Time Cost

21min53s

Code

• My Solution

  class Solution {
  public:
    int characterReplacement(string s, int k) {
        int base = 1, ceil = s.length();
        int window = (base + ceil) / 2, result = 0;
  
        vector<vector<int>> counts(s.length() + 1, vector<int>(26, 0));
  
        for (int i=0; i<s.length(); i++) {
            counts[i + 1] = counts[i];
            counts[i + 1][s[i] - 'A']++;
        }
  
        bool isqualified = false;
  
        while (base <= ceil) {
            for (int i=0; i<=s.length()-window; i++) {
                // start: i+1, end:i+window
                int max_letter = 0;
                vector<int> cur = vector_sub(counts[i+window], counts[i]);
                for (int num: cur) {
                    max_letter = std::max(max_letter, num);
                }
                if (window - max_letter <= k) {
                    // qualified
                    result = window;
                    isqualified = true;
                    base = window + 1;
                    window = (base + ceil) / 2;
                    break;
                }
            }
            if (!isqualified) {
                ceil = window - 1;
                window = (base + ceil) / 2;
            }
            isqualified = false;
        }
  
        return result;
    }
  
    // a-b
    vector<int> vector_sub(vector<int> a, vector<int> b) {
        vector<int> result;
        for (int i=0; i<a.size(); i++) {
            result.push_back(a[i] - b[i]);
        }
        return result;
    }
  };
  

• Good Solution

  class Solution {
  public:
    int characterReplacement(string s, int k) {
        int h[26] = {0};
        int l = 0;
        int maxf = 0;   
        int ans = 0;
  
        for (int r = 0; r < (int)s.size(); r++) {
            int idx = s[r] - 'A';
            h[idx]++;
            maxf = max(maxf, h[idx]);
            while (r - l + 1 - maxf > k) {
                h[s[l] - 'A']--;
                l++;
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
  };