题目

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

示例：

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

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

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

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

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

解答 & 代码

滑动窗口

注意：在选择窗口中出现次数最多的字符时，如果遇到两个字符的出现次数相同，要选择在整个字符串 text 中出现次数最多的那个字符。否则对于 "ac**ba**aa" 这个样例，正确答案应为 4，但会得到错误答案 3，应为当窗口为 ba 时，将 b 当作了出现次数最对的字符，而在 text 中 b 总共只出现一次，无法完成替换，因此会收缩窗口，但实际不需要收缩窗口，应该将 a 当作出现次数最多的字符

class Solution {
private:
    unordered_map<char, int> textDict;
    // 返回 window 中出现次数最多的字符
    char mostCommonChar(unordered_map<char, int> window)
    {
        char result = ' ';
        int maxCnt = 0;
        for(auto it = window.begin(); it != window.end(); ++it)
        {
            // 如果两个字符出现次数一样多，选择在整个字符串 text 中出现次数最多的字符
            if(it->second > maxCnt || 
                (it->second == maxCnt && textDict[it->first] > textDict[result]))
            {
                maxCnt = it->second;
                result = it->first;
            }
        }
        return result;
    }
public:
    int maxRepOpt1(string text) {
        int len = text.size();
        for(int i = 0; i < len; ++i)        // 统计字符串 text 中各个字符的个数
            ++textDict[text[i]];

        int result = 0;
        unordered_map<char, int> window;    // 窗口，key = 字符，val = 出现次数
        int left = 0;
        int right = 0;
        while(right < len)
        {
            char ch = text[right];
            ++window[ch];
            ++right;

            char mostCommonCh = mostCommonChar(window);    // 窗口中出现次数最多的字符
            int mostCommonChCnt = window[mostCommonCh];    // 窗口中出现次数最多的字符的出现次数
            // 收缩窗口的条件，如果：
            // a. 窗口中其他字符的总的出现次数 > 1，则无法只换一次，需要收缩窗口
            // b. 窗口长度大于 mostCommonCh 在 text 中的总个数，则窗口外的字符不够替换，需要收缩窗口
            while(right - left - mostCommonChCnt > 1 || right - left > textDict[mostCommonCh])
            {
                char deleteCh = text[left];
                --window[deleteCh];
                if(window[deleteCh] == 0)
                    window.erase(deleteCh);
                ++left;

                mostCommonCh = mostCommonChar(window);
                mostCommonChCnt = window[mostCommonCh];
            }

            // 更新结果
            result = max(result, right - left);
        }
        return result;
    }
};

复杂度分析：设字符串 text 长为 N，不同字符的种数为 C

时间复杂度 O(N)：最坏情况下，字符串 text 的每个字符分别被左、右指针遍历一次，时间复杂度 O(N)；寻找窗口内出现次数最多的字符的时间复杂度为 O(1)，因为哈希表 window 的长度不会超过 3
空间复杂度 O(C)：哈希表 textDict 的空间复杂度都取决于字符串text 中不同字符的种数 C；哈希表 window 的长度不会超过 3，因此空间复杂度 O(1)

执行结果：

执行结果：通过

执行用时：108 ms, 在所有 C++ 提交中击败了 5.03% 的用户
内存消耗：41.9 MB, 在所有 C++ 提交中击败了 5.03% 的用户

hot 100

[中等] 1156. 单字符重复子串的最大长度

题目

解答 & 代码