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" with length 3.
Example 2:
1
2
3
4
5
Input:
text = "aaabaaa"
Output:
6
Explanation: Swap 'b' with the last 'a' (or the first 'a'), and we get longest repeated character substring "aaaaaa" with length 6.
Example 3:
1
2
3
4
5
Input:
text = "aaaaa"
Output:
5
Explanation: No need to swap, longest repeated character substring is "aaaaa" with length is 5.
The key is to find the longest substring of repeated characters, possibly by swapping one character from elsewhere in the string. We can group consecutive same characters and, for each group, check if we can extend it by swapping in another occurrence of the same character from outside the group.
classSolution {
public:int maxRepOpt1(string text) {
vector<int> cnt(26, 0);
for (char c : text) cnt[c -'a']++;
int ans =0, n = text.size();
for (int i =0; i < n;) {
int j = i;
while (j < n && text[j] == text[i]) j++;
int len = j - i;
int k = j +1;
while (k < n && text[k] == text[i]) k++;
int merged = len;
if (j < n && j +1< n && text[j +1] == text[i]) {
int l2 =0, t = j +1;
while (t < n && text[t] == text[i]) { l2++; t++; }
merged += l2;
}
ans = max(ans, min(cnt[text[i] -'a'], merged + (merged > len ?0:1)));
ans = max(ans, min(cnt[text[i] -'a'], len + (cnt[text[i] -'a'] > len ?1:0)));
i = j;
}
return ans;
}
};
classSolution {
publicintmaxRepOpt1(String text) {
int[] cnt =newint[26];
for (char c : text.toCharArray()) cnt[c -'a']++;
int ans = 0, n = text.length();
for (int i = 0; i < n;) {
int j = i;
while (j < n && text.charAt(j) == text.charAt(i)) j++;
int len = j - i;
int merged = len;
if (j < n - 1 && text.charAt(j + 1) == text.charAt(i)) {
int k = j + 1;
while (k < n && text.charAt(k) == text.charAt(i)) k++;
merged += k - (j + 1);
}
ans = Math.max(ans, Math.min(cnt[text.charAt(i) -'a'], merged < cnt[text.charAt(i) -'a']? merged + 1 : merged));
ans = Math.max(ans, Math.min(cnt[text.charAt(i) -'a'], len < cnt[text.charAt(i) -'a']? len + 1 : len));
i = j;
}
return ans;
}
}
classSolution {
funmaxRepOpt1(text: String): Int {
val cnt = IntArray(26)
for (c in text) cnt[c - 'a']++var ans = 0var i = 0val n = text.length
while (i < n) {
var j = i
while (j < n && text[j] == text[i]) j++val len = j - i
var merged = len
if (j < n - 1&& text[j + 1] == text[i]) {
var k = j + 1while (k < n && text[k] == text[i]) k++ merged += k - (j + 1)
}
ans = maxOf(ans, minOf(cnt[text[i] - 'a'], if (merged < cnt[text[i] - 'a']) merged + 1else merged))
ans = maxOf(ans, minOf(cnt[text[i] - 'a'], if (len < cnt[text[i] - 'a']) len + 1else len))
i = j
}
return ans
}
}
classSolution:
defmaxRepOpt1(self, text: str) -> int:
from collections import Counter
cnt = Counter(text)
ans =0 n = len(text)
i =0while i < n:
j = i
while j < n and text[j] == text[i]:
j +=1 length = j - i
merged = length
if j < n -1and text[j +1] == text[i]:
k = j +1while k < n and text[k] == text[i]:
k +=1 merged += k - (j +1)
ans = max(ans, min(cnt[text[i]], merged + (1if merged < cnt[text[i]] else0)))
ans = max(ans, min(cnt[text[i]], length + (1if length < cnt[text[i]] else0)))
i = j
return ans
use std::collections::HashMap;
impl Solution {
pubfnmax_rep_opt1(text: String) -> i32 {
let cnt = text.chars().fold(HashMap::new(), |mut m, c| { *m.entry(c).or_insert(0) +=1; m });
let s: Vec<char>= text.chars().collect();
let n = s.len();
letmut ans =0;
letmut i =0;
while i < n {
letmut j = i;
while j < n && s[j] == s[i] { j +=1; }
let len = j - i;
letmut merged = len;
if j < n -1&& s[j +1] == s[i] {
letmut k = j +1;
while k < n && s[k] == s[i] { k +=1; }
merged += k - (j +1);
}
let total =*cnt.get(&s[i]).unwrap();
ans = ans.max(std::cmp::min(total, merged +if merged < total { 1 } else { 0 }));
ans = ans.max(std::cmp::min(total, len +if len < total { 1 } else { 0 }));
i = j;
}
ans asi32 }
}