*424. Longest Repeating Character Replacement [Medium]

424. Longest Repeating Character Replacement

You are given a string s and an integer k. You can choose any character of the string and change it to any other uppercase English character. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Constraints:

• 1 <= s.length <= 10^5
• s consists of only uppercase English letters.
• 0 <= k <= s.length

Example

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.

思路

在取最长连续子串的基础上加了一个忽略k个字符的条件

题解

    public int characterReplacement(String s, int k) {
        char[] data = s.toCharArray();
        int max, left, result;
        result = left = max = 0;
	// 用来保存在当前截取字符串中每一个字符的数量
        HashMap<Character, Integer> recordMap = new HashMap<>();

        for (int i = 0; i < data.length; i++) {
	    // 遍历新字符+1
            recordMap.put(data[i], recordMap.getOrDefault(data[i], 0) + 1);
	    // 获取当前截取字符串中最大的那个字符的数量
            max = Math.max(max, recordMap.get(data[i]));
	    // 如果当前截取字符串的长度已经大于 最大字符数+k，那么肯定没法满足重复字符串的条件了
            if (max + k < (i - left + 1)) {
		// 左指针开始右移，Map中也删除改记录
                recordMap.put(data[left], recordMap.get(data[left]) - 1);
                left++;
            } else {
		// 否则就记录当前结果，因为上面取得是Map中最大的字符数，所以这里结果肯定也是最大的
                result = i - left + 1;
            }
        }
        return result;
    }