Longest Repeating Character Replacement

Difficulty: Medium
Link: https://leetcode.com/problems/longest-repeating-character-replacement/

Problem

Explanation

• 这道题目我自己没有想到解法，是看了LeetCode上的讨论之后明白的。中心思想就是滑动窗口，通过往s[i:j]窗口中不断添加新的字符，如果符合条件则继续添加（扩大窗口的大小），而不符合条件的话，则将窗口的起始位置i + 1，即将窗口右滑。最终求的结果是连续的相同字符子串的长度，所以就如同是一个不断开的连续窗口。
• 之前我陷入的误区，是如何替换字母，其实根本不应该去考虑去替换字符串，应该考虑最终的结果。因为最终的结果必定是子串s[i:j], i >= 0, j < s.size()，从结果考虑的话，最终符合的条件就是j - i - *max_element(alp + 65, alp + 91) <= k
*max_element(alp + 65, alp + 91)就是在s[i:j]范围内，字母A-Z中数量最大的字符的数量，例如"AAABCC"，结果就是3。取这个值的原因是：这样可以通过替换最少的字母而达到最长的重复字符子串)

cpp solution

class Solution {
public:
    int characterReplacement(string s, int k) {
        int i = 0, j = 0, alp[91] = {};
        while (j < s.length()) {
            alp[s[j++]]++;
            if ((j - i - *max_element(alp + 65, alp + 91)) > k) {
                alp[s[i++]]--;
            }
        }
        return j - i;
    }
};