题目链接

英文链接：https://leetcode.com/problems/swap-for-longest-repeated-character-substring/

中文链接：https://leetcode-cn.com/problems/swap-for-maximum-repeated-substring/

题目详述

如果字符串中的所有字符都相同，那么这个字符串是单字符重复的字符串。

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

示例 5：

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

提示：

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

题目详解

滑动窗口，窗口内最多可以容忍一个不同的字符。类似于 LeetCode424-替换后的最长重复字符。
需要注意可能没有足够的字符进行交换，也就是最长不能超过该字符的个数。

public class LeetCode_01156 {

    public int maxRepOpt1(String text) {
        char[] cs = text.toCharArray();
        int[] cnt = new int[26];
        for (char c : cs) {
            ++cnt[c - 'a'];
        }
        int res = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            res = Math.max(res, process(c, cs, cnt));
        }
        return res;
    }

    private int process(char cur, char[] cs, int[] cnt) {
        int res = 0;
        for (int l = 0, r = 0, other = 0; r < cs.length; ) {
            if (cs[r++] != cur) {
                ++other;
                while (other > 1) {
                    if (cs[l++] != cur) {
                        --other;
                    }
                }
            }
            res = Math.max(res, r - l);
        }
        res = Math.min(res, cnt[cur - 'a']);
        return res;
    }
}

换一种思考方式，可以运用动态规划。
用 f(i) 表示没有交换过字符以位置 i 结尾的个数，用 g(i) 表示最多交换过一个字符以位置 i 结尾的个数。
指定一种字符
- 当前字符等于指定字符时， f(i) = f(i - 1) + 1，g(i) = g(i - 1) + 1。
- 当前字符不等于指定字符时， g(i) = f(i - 1) + 1，f(i) = 0。
- 每次用 g(i) 更新结果。
- 可以运用状态压缩将两个数组压缩成两个变量。
同样需要注意可能没有足够的字符进行交换，也就是最长不能超过该字符的个数。

public class LeetCode_01156 {
    
    public int maxRepOpt1(String text) {
        char[] cs = text.toCharArray();
        int res = 0;
        for (char c = 'a'; c <= 'z'; ++c) {
            res = Math.max(res, process(c, cs));
        }
        return res;
    }

    private int process(char cur, char[] cs) {
        int f = 0, g = 0;
        int cnt = 0;
        int res = 0;
        for (char c : cs) {
            if (c == cur) {
                ++f;
                ++g;
                ++cnt;
            } else {
                g = f + 1;
                f = 0;
            }
            res = Math.max(res, g);
        }
        res = Math.min(res, cnt);
        return res;
    }
}