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

Problem

Explanation

• 這道題目我自己沒有想到解法，是看了LeetCode上的討論之后明白的。中心思想就是滑動窗口，通過往s[i:j]窗口中不斷添加新的字符，如果符合條件則繼續(xù)添加（擴大窗口的大?。?，而不符合條件的話，則將窗口的起始位置i + 1，即將窗口右滑。最終求的結(jié)果是連續(xù)的相同字符子串的長度，所以就如同是一個不斷開的連續(xù)窗口。
• 之前我陷入的誤區(qū)，是如何替換字母，其實根本不應該去考慮去替換字符串，應該考慮最終的結(jié)果。因為最終的結(jié)果必定是子串s[i:j], i >= 0, j < s.size()，從結(jié)果考慮的話，最終符合的條件就是j - i - *max_element(alp + 65, alp + 91) <= k
*max_element(alp + 65, alp + 91)就是在s[i:j]范圍內(nèi)，字母A-Z中數(shù)量最大的字符的數(shù)量，例如"AAABCC"，結(jié)果就是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;
    }
};