https://leetcode.com/problems/swap-for-longest-repeated-character-substring/
Given a string
text, we are allowed to swap two of the characters in the string. Find the length of the longest substring with repeated characters.
Example 1:
Input: text = "ababa" Output: 3 Explanation: We can swap the first 'b' with the last 'a', or the last 'b' with the first 'a'. Then, the longest repeated character substring is "aaa", which its length is 3.
Example 2:
Input: text = "aaabaaa" Output: 6 Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa", which its length is 6.
Example 3:
Input: text = "aaabbaaa" Output: 4
Example 4:
Input: text = "aaaaa" Output: 5 Explanation: No need to swap, longest repeated character substring is "aaaaa", length is 5.
Example 5:
Input: text = "abcdef" Output: 1
Constraints:
1 <= text.length <= 20000textconsist of lowercase English characters only
X. https://leetcode.com/problems/swap-for-longest-repeated-character-substring/discuss/355852/Python-Groupby
There are only 2 cases that we need to take care of:
- extend the group by 1
- merge 2 adjacent groups together, which are separated by only 1 character
Explanation
For
With these two data, calculate the best solution for the two cases above.
S = "AAABBCB"[[c, len(list(g))] for c, g in groupby(S)] --> [[A,3],[B,2],[C,1],[B,1]]collections.Counter(S) --> {A:3, B:3, C:1}With these two data, calculate the best solution for the two cases above.
Complexity
Time
Space
O(N)Space
O(N)
Python:
commented by @henry34
commented by @henry34
def maxRepOpt1(self, S):
# We get the group's key and length first, e.g. 'aaabaaa' -> [[a , 3], [b, 1], [a, 3]
A = [[c, len(list(g))] for c, g in itertools.groupby(S)]
# We also generate a count dict for easy look up e.g. 'aaabaaa' -> {a: 6, b: 1}
count = collections.Counter(S)
# only extend 1 more, use min here to avoid the case that there's no extra char to extend
res = max(min(k + 1, count[c]) for c, k in A)
# merge 2 groups together
for i in xrange(1, len(A) - 1):
# if both sides have the same char and are separated by only 1 char
if A[i - 1][0] == A[i + 1][0] and A[i][1] == 1:
# min here serves the same purpose
res = max(res, min(A[i - 1][1] + A[i + 1][1] + 1, count[A[i + 1][0]]))
return res
Collect indexes for each character. Then, count the number of consecutive indices
cnt, and track the number of previous consecutive indices cnt1.Note that we setcnt1to zero if the gap is larger than one.
In the end, we'll get a max count of the repeated characters with no more than one-character gap. If we have more of that character somewhere in the string (
idx[n].size() > mx), we add 1 for the swap operation.int maxRepOpt1(string text, int res = 1) {
vector<vector<int>> idx(26);
for (auto i = 0; i < text.size(); ++i) idx[text[i] - 'a'].push_back(i);
for (auto n = 0; n < 26; ++n) {
auto cnt = 1, cnt1 = 0, mx = 0;
for (auto i = 1; i < idx[n].size(); ++i) {
if (idx[n][i] == idx[n][i - 1] + 1) ++cnt;
else {
cnt1 = idx[n][i] == idx[n][i - 1] + 2 ? cnt : 0;
cnt = 1;
}
mx = max(mx, cnt1 + cnt);
}
res = max(res, mx + (idx[n].size() > mx ? 1 : 0));
}
return res;
}X. https://www.acwing.com/solution/LeetCode/content/3718/
给定一个字符串 text，允许交换字符串中的任意两个字符。找到最长的单字符重复的子串的长度。
(动态规划)
- 我们分别考察每种字符所能得到的最大答案。
- 假设我们当前考察的是字符
c。我们通过遍历一次数组的方式，找到单字符就是c的情况下的最长单重复子串。 - 设
cnt为字符串中c出现的次数； 表示以 i 结尾且没有替换过不是c的字符时的最长但重复子串； 表示以 i 结尾且替换过不是c的字符时的最长但重复子串。 - 当
c == text[i]时，累加cnt，，，也就是都可以沿着上一次的结果往后累加 1 的长度。 - 如果
c != text[i]，则 ，表示我们强制替换text[i]的字符为c（注意不是交换），所以要从没有替换过的 f 数组转移；，表示如果不替换，那么长度只能归 0。交换只是替换的一种特殊形式，我们都先假设总能交换。如果不能交换，如aaabaaa我们无法把中间的b用一个新的a交换时，可以通过答案不能超过cnt来特判。 - 答案为 ，也就是所有的 f 和 g 的最大值，但结果不能超过
cnt。 - 这里的 f 和 g 数组因为之和上一位有关，所以可以化简为变量。
时间复杂度
- 枚举每种字符时，只需要遍历数组一次，故时间复杂度为 。
空间复杂度
- 优化后，只需要常数个变量，故空间复杂度为
int solve(char c, const string& text) {
int n = text.length(), tot = 0;
int f = 0, g = 0, cnt = 0;
for (int i = 0; i < n; i++) {
if (c == text[i]) {
f++;
g++;
cnt++;
} else {
g = f + 1;
f = 0;
}
tot = max(tot, max(f, g));
}
return min(tot, cnt);
}
int maxRepOpt1(string text) {
int ans = 0;
for (char c = 'a'; c <= 'z'; c++)
ans = max(ans, solve(c, text));
return ans;
}
Pre-processing
- Compute the longest repeated substring starts and ends with text[i].
- Count the frequency of each letter.
Main
- Loop through each letter
- Check the left and right letter
- if they are the same, len = left + right
- e.g1. “aa c aaa [b] aaaa” => len = 3 + 4 = 7
- if they are not the same, len = max(left, right)
- e.g2. “aa [b] ccc d c” => len = max(2, 3) = 3
- if they are the same, len = left + right
- If the letter occurs more than len times, we can always find an extra one and swap it with the current letter => ++len
- e.g.1, count[“a”] = 9 > 7, len = 7 + 1 = 8
- e.g.2, count[“c”] = 4 > 3, len = 3 + 1 = 4
Time complexity: O(n)
Space complexity: O(n)
X. https://leetcode.com/problems/swap-for-longest-repeated-character-substring/discuss/355866/Intuitive-Java-Solution-With-ExplanationSpace complexity: O(n)
public int maxRepOpt1(String s) {
int[] freq = new int[26];
char[] ch = s.toCharArray();
for(int i=0; i < ch.length; i++)
freq[ch[i]-'a']++;
int max = 0;
for(int i=0; i < ch.length; i++){
char curr = ch[i];
int j=i, count = 0, diff = 0;
while(j < ch.length && (curr == ch[j] || diff == 0) && count < freq[curr-'a']){
if(curr != ch[j])
++diff;
++count;
++j;
}
max = Math.max(max, count);
}
for(int i=ch.length-1; i >= 0; i--){
char curr = ch[i];
int j=i, count = 0, diff = 0;
while(j >= 0 && (curr == ch[j] || diff == 0) && count < freq[curr-'a']){
if(curr != ch[j])
++diff;
++count;
--j;
}
max = Math.max(max, count);
}
return max;
}
LeetCode 424
class Solution {
public int characterReplacement(String s, int k) {
int len = s.length();
int[] count = new int[26];
int start = 0, maxCount = 0, maxLength = 0;
for (int end = 0; end < len; end++) {
maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
while (end - start + 1 - maxCount > k) {
count[s.charAt(start) - 'A']--;
start++;
maxCount = 0;
for(int i = 0; i < 26; i++){
if(maxCount < count[i]){
maxCount = count[i];
}
}
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
}
LeetCode 1156
In this case, just set k=1.
In this case, just set k=1.
class Solution {
public int maxRepOpt1(String s) {
int len = s.length();
int[] count = new int[26];
int[] newCount = new int[26];
for(char c:s.toCharArray()) newCount[c-'a']++;
int start = 0, maxCount = 0, maxLength = 0;
for (int end = 0; end < len; end++) {
maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'a']);
while (end - start + 1 - maxCount > 1 || end - start + 1>newCount[s.charAt(start)-'a']) {
count[s.charAt(start) - 'a']--;
start++;
// maxCount = Math.max(count[s.charAt(end)-'a'],count[s.charAt(start)-'a']);
maxCount=0;
for(int i = 0; i < 26; i++){
if(maxCount < count[i]){
maxCount = count[i];
}
}
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
}
The idea is to keep track of all repeated character segments and see if the neighbor segments (segments separated by one other character) can be merged:
- There exist a third segment with same character, swap a same character from a third segment. Merged length =
len(segment1) + 1 + len(segment2) - There does not exist a third segment with same character, swap a character from the first character of the first segment, or swapping the last character from the second segment, to the separating index. Merged length =
len(segment1) + len(segment2)
Otherwise, if there are multiple segments of a character but they are not neighbor, we can only swap a character from one to the other. New length =
len(segment) + 1 public int maxRepOpt1(String text) {
Map<Character, List<int[]>> substrs = new HashMap<>();
int l = 0, r = 0, res = 0, n = text.length();
// Put all character segments in the hashmap
while(r < n) {
while(r < n && text.charAt(r) == text.charAt(l)) r++;
res = Math.max(res, r - l);
substrs.computeIfAbsent(text.charAt(l), k -> new ArrayList<>()).add(new int[]{l, r - 1});
l = r;
}
for(char ch : substrs.keySet()) {
List<int[]> indexes = substrs.get(ch);
for(int j = 0; j < indexes.size() - 1; j++) {
int[] ind1 = indexes.get(j), ind2 = indexes.get(j + 1);
int len1 = ind1[1] - ind1[0] + 1, len2 = ind2[1] - ind2[0] + 1;
if(ind1[1] + 1 == ind2[0] - 1) // neighbor segments
res = Math.max(res, (indexes.size() > 2 ? 1 : 0) + len1 + len2);
else // not neighbor, swap a char to the longer one
res = Math.max(res, Math.max(len1, len2) + 1);
}
}
return res;
}