main.cpp

// Source: https://leetcode.com/problems/longest-repeating-character-replacement
// Title: Longest Repeating Character Replacement
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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.
//
// **Example 1:**
//
// ```
// Input: s = "ABAB", k = 2
// Output: 4
// Explanation: Replace the two 'A's with two 'B's or vice versa.
// ```
//
// **Example 2:**
//
// ```
// 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.
// There may exists other ways to achieve this answer too.```
//
// **Constraints:**
//
// - `1 <= s.length <= 10^5`
// - `s` consists of only uppercase English letters.
// - `0 <= k <= s.length`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <string>

using namespace std;

// Sliding Window
//
// Try all letters.
// Find the maximum subarray with at most k letters other than current letter.
class Solution {
 public:
  int characterReplacement(string s, int k) {
    int n = s.size();

    auto ans = 0;
    for (auto c = 'A'; c <= 'Z'; ++c) {
      auto l = 0, r = 0;  // [l, r)
      auto count = 0;
      while (r < n) {
        if (s[r] != c) ++count;
        ++r;

        while (count > k) {
          if (s[l] != c) --count;
          ++l;
        }

        ans = max(ans, r - l);
      }
    }

    return ans;
  }
};