Description
1156. Swap For Longest Repeated Character Substring (Medium)
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 * 10⁴textconsist of lowercase English characters only.
Solution
The problem can be solved using a dual-pointer approach. Firstly, we can utilize an array called $cnt$ to track the frequency of each character in the given text.
Next, we establish three pointers: $i$, $j$, and $k$. Initially, all pointers are set to 0. We increment $j$ until $text[j]$ is not equal to $text[i]$. Then, we set $k = j + 1$ and continue incrementing $k$ until $text[k]$ is not equal to $text[i]$. At this point, we can calculate a partial result: $res = \max(res, \min(k - i, cnt[text[i]]))$. Afterwards, we update $i = j$ and repeat the above steps until $i >= text.size()$.
Code
class Solution {
public:
int maxRepOpt1(string text) {
int n = text.size();
vector<int> prefix(26);
for (int i = 1; i <= n; ++i) {
int c = text[i - 1] - 'a';
for (int j = 0; j < 26; ++j) {
if (j == c) {
prefix[j] = prefix[j] + 1;
}
}
}
int res = 0;
int i = 0, j = 0, k = 0;
while (i < n) {
while (j < n && text[j] == text[i]) {
++j;
}
k = j + 1;
while (k < n && text[k] == text[i]) {
++k;
}
res = max(res, min(k - i, prefix[text[i] - 'a']));
i = j;
}
return res;
}
};