问题描述 链接到标题

1156. 单字符重复子串的最大长度 (Medium) 如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字 符串。

给你一个字符串 text，你只能交换其中两个字符一次或者什么都 不做，然后得到一些单字符重复的子串。返回其中最长的子串的长度 。

示例 1：

输入：text = "ababa"
输出：3

示例 2：

输入：text = "aaabaaa"
输出：6

示例 3：

输入：text = "aaabbaaa"
输出：4

示例 4：

输入：text = "aaaaa"
输出：5

示例 5：

输入：text = "abcdef"
输出：1

提示：

  • 1 <= text.length <= 20000
  • text 仅由小写英文字母组成。

解题思路 链接到标题

可以利用双指针解决，我们先用数组 $cnt$ 统计 $text$ 中每个字符的出现的次数。

然后我们定一个三个指针，分别为 $i$，$j$，$k$。初始时都为 $0$，然后我们让 $j$ 右移，直到 $text[j] \neq text[i]$，然后令 $k = j + 1$，再右移 $k$，直到 $text[k] \neq text[i]$，这里可以统计一次结果，$res = \max(res, \min(k - i, cnt[text[i]]))$，然后令 $i = j$，重复以上步骤直到 $i >= text.size()$。

代码 链接到标题 

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