题目描述

给定一个字符串 text，允许交换字符串中的任意两个字符。找到最长的单字符重复的子串的长度。

样例

输入：text = "ababa"
输出：3
解释：我们可以交换第一个 'b' 和最后一个 'a'，或者第一个 'a' 和最后一个 'b'。
然后，最长的单字符重复的子串 "aaa" 的长度就是 3。

输入：text = "aaabaaa"
输出：6
解释：交换 'b' 和最后一个 'a' （或第一个 'a'），
我们得到最长的单字符重复的子串 "aaaaaa" 的长度就是 6

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

输入：text = "aaaaa"
输出：5
解释：没有必要交换字符，我们得到的最长的单字符重复的子串就是 "aaaaa"，长度为 5。

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

限制

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

算法

(动态规划) $O(n)$

1. 我们分别考察每种字符所能得到的最大答案。
2. 假设我们当前考察的是字符 c。我们通过遍历一次数组的方式，找到单字符就是 c 的情况下的最长单重复子串。
3. 设 cnt 为字符串中 c 出现的次数；$f(i)$ 表示以 $i$ 结尾且没有替换过不是 c 的字符时的最长但重复子串；$g(i)$ 表示以 $i$ 结尾且替换过不是 c 的字符时的最长但重复子串。
4. 当 c == text[i] 时，累加 cnt，$f(i) = f(i - 1) + 1$，$g(i) = g(i - 1) + 1$，也就是都可以沿着上一次的结果往后累加 1 的长度。
5. 如果 c != text[i]，则 $g(i) = f(i - 1) + 1$，表示我们强制替换 text[i] 的字符为 c （注意不是交换），所以要从没有替换过的 $f$ 数组转移；$f(i) = 0$，表示如果不替换，那么长度只能归 0。交换只是替换的一种特殊形式，我们都先假设总能交换。如果不能交换，如 aaabaaa 我们无法把中间的 b 用一个新的 a 交换时，可以通过答案不能超过 cnt 来特判。
6. 答案为 $\min(cnt, max(f(i), g(i)))$，也就是所有的 $f$ 和 $g$ 的最大值，但结果不能超过 cnt。
7. 这里的 $f$ 和 $g$ 数组因为之和上一位有关，所以可以化简为变量。

时间复杂度

• 枚举每种字符时，只需要遍历数组一次，故时间复杂度为 $O(n)$。

空间复杂度

• 优化后，只需要常数个变量，故空间复杂度为 $O(1)$。

C++ 代码

class Solution {
public:
    int solve(char c, const string& text) {
        int n = text.length(), tot = 0;
        int f = 0, g = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (c == text[i]) {
                f++;
                g++;
                cnt++;
            } else {
                g = f + 1;
                f = 0;
            }
            tot = max(tot, max(f, g));
        }

        return min(tot, cnt);
    }

    int maxRepOpt1(string text) {
        int ans = 0;
        for (char c = 'a'; c <= 'z'; c++)
            ans = max(ans, solve(c, text));
        return ans;
    }
};