Description Link to heading

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⁴
  • text consist of lowercase English characters only.

Solution Link to heading

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 Link to heading 

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;
    }
};