Description#
You are given a string text. You can swap two of the characters in the text.
Return 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" with length 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" with length 6.
Example 3:
Input: text = "aaaaa"
Output: 5
Explanation: No need to swap, longest repeated character substring is "aaaaa" with length is 5.
Constraints:
1 <= text.length <= 2 * 104text consist of lowercase English characters only.
Solutions#
Solution 1: Two Pointers#
First, we use a hash table or array $cnt$ to count the occurrence of each character in the string $text$.
Next, we define a pointer $i$, initially $i = 0$. Each time, we set the pointer $j$ to $i$, and continuously move $j$ to the right until the character pointed by $j$ is different from the character pointed by $i$. At this time, we get a substring $text[i..j-1]$ of length $l = j - i$, where all characters are the same.
Then we skip the character pointed by the pointer $j$, and continue to move the pointer $k$ to the right until the character pointed by $k$ is different from the character pointed by $i$. At this time, we get a substring $text[j+1..k-1]$ of length $r = k - j - 1$, where all characters are the same. So the longest single-character repeated substring we can get by at most one swap operation is $\min(l + r + 1, cnt[text[i]])$. Next, we move the pointer $i$ to $j$ and continue to find the next substring. We take the maximum length of all substrings that meet the conditions.
The time complexity is $O(n)$, and the space complexity is $O(C)$. Here, $n$ is the length of the string, and $C$ is the size of the character set. In this problem, $C = 26$.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution:
def maxRepOpt1(self, text: str) -> int:
cnt = Counter(text)
n = len(text)
ans = i = 0
while i < n:
j = i
while j < n and text[j] == text[i]:
j += 1
l = j - i
k = j + 1
while k < n and text[k] == text[i]:
k += 1
r = k - j - 1
ans = max(ans, min(l + r + 1, cnt[text[i]]))
i = j
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| class Solution {
public int maxRepOpt1(String text) {
int[] cnt = new int[26];
int n = text.length();
for (int i = 0; i < n; ++i) {
++cnt[text.charAt(i) - 'a'];
}
int ans = 0, i = 0;
while (i < n) {
int j = i;
while (j < n && text.charAt(j) == text.charAt(i)) {
++j;
}
int l = j - i;
int k = j + 1;
while (k < n && text.charAt(k) == text.charAt(i)) {
++k;
}
int r = k - j - 1;
ans = Math.max(ans, Math.min(l + r + 1, cnt[text.charAt(i) - 'a']));
i = j;
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
| class Solution {
public:
int maxRepOpt1(string text) {
int cnt[26] = {0};
for (char& c : text) {
++cnt[c - 'a'];
}
int n = text.size();
int ans = 0, i = 0;
while (i < n) {
int j = i;
while (j < n && text[j] == text[i]) {
++j;
}
int l = j - i;
int k = j + 1;
while (k < n && text[k] == text[i]) {
++k;
}
int r = k - j - 1;
ans = max(ans, min(l + r + 1, cnt[text[i] - 'a']));
i = j;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| func maxRepOpt1(text string) (ans int) {
cnt := [26]int{}
for _, c := range text {
cnt[c-'a']++
}
n := len(text)
for i, j := 0, 0; i < n; i = j {
j = i
for j < n && text[j] == text[i] {
j++
}
l := j - i
k := j + 1
for k < n && text[k] == text[i] {
k++
}
r := k - j - 1
ans = max(ans, min(l+r+1, cnt[text[i]-'a']))
}
return
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| function maxRepOpt1(text: string): number {
const idx = (c: string) => c.charCodeAt(0) - 'a'.charCodeAt(0);
const cnt: number[] = new Array(26).fill(0);
for (const c of text) {
cnt[idx(c)]++;
}
let ans = 0;
let i = 0;
const n = text.length;
while (i < n) {
let j = i;
while (j < n && text[j] === text[i]) {
++j;
}
const l = j - i;
let k = j + 1;
while (k < n && text[k] === text[i]) {
++k;
}
const r = k - j - 1;
ans = Math.max(ans, Math.min(cnt[idx(text[i])], l + r + 1));
i = j;
}
return ans;
}
|
