单字符重复子串的最大长度
难度:
标签:
题目描述
代码结果
运行时间: 43 ms, 内存: 17.3 MB
/*
* Problem Statement: Given a string text, you can swap two characters once or do nothing to form substrings of repeated characters. Return the length of the longest such substring.
*
* Approach using Java Stream:
* 1. Use a stream to create groups of consecutive identical characters.
* 2. Calculate maximum possible lengths similar to the standard approach.
* 3. Return the maximum length found.
*/
import java.util.*;
import java.util.stream.Collectors;
public class Solution {
public int maxRepOpt1(String text) {
int n = text.length();
if (n <= 1) return n;
Map<Character, Long> countMap = text.chars().mapToObj(c -> (char)c)
.collect(Collectors.groupingBy(c -> c, Collectors.counting()));
List<int[]> groups = new ArrayList<>();
int i = 0;
while (i < n) {
int j = i;
while (j < n && text.charAt(j) == text.charAt(i)) j++;
groups.add(new int[]{text.charAt(i) - 'a', j - i});
i = j;
}
return groups.stream().mapToInt(group -> {
int currentChar = group[0];
int groupLen = group[1];
int maxLen = groupLen;
if (countMap.get((char)(currentChar + 'a')) > groupLen) {
maxLen = Math.max(maxLen, groupLen + 1);
}
for (int k = 0; k < groups.size() - 2; k++) {
if (groups.get(k + 1)[1] == 1 && groups.get(k + 2)[0] == currentChar) {
maxLen = Math.max(maxLen, groupLen + groups.get(k + 2)[1]);
if (countMap.get((char)(currentChar + 'a')) > groupLen + groups.get(k + 2)[1]) {
maxLen = Math.max(maxLen, groupLen + groups.get(k + 2)[1] + 1);
}
}
}
return maxLen;
}).max().orElse(0);
}
}
解释
方法:
题解的主要思路是通过动态规划和额外的统计数组来解决问题。首先,使用一个数组 `appear_times` 来记录每个字符在文本中出现的次数。同时,使用两个数组 `max_consec` 和 `max_gap` 分别记录每个字符连续出现的最大长度和可能通过一次交换后能达到的最大长度。动态规划数组 `dp` 的每个元素包含两个值,分别表示当前位置连续的字符长度和可能的最长交换后长度。在遍历字符串时,根据当前字符是否与前一个字符相同来更新 `dp` 数组,以及对应的 `max_consec` 和 `max_gap`。最后,根据字符的出现次数,利用 `max_consec` 和 `max_gap` 计算可能的最大长度。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在代码中`dp`数组的每个元素包含两个值,其中第二个值是如何计算的,特别是在字符不连续时?
▷🦆
题解中提到`可能通过一次交换后能达到的最大长度`,具体是如何确定一个字符通过交换可以增加的最大长度?
▷🦆
为什么在更新`max_gap`数组时使用`dp[i][1]`的值,这里的逻辑是什么?
▷🦆
代码中对于只出现一次的字符,返回的最大长度直接是`max_consec[i]`,这是否意味着对于单个字符的交换没有考虑?
▷