# Longest Repeating Character Replacement
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-repeating-character-replacement)
Canonical: https://scaleengineer.com/dsa/problems/longest-repeating-character-replacement
**Patterns:** [Sliding Window](https://scaleengineer.com/dsa/patterns/sliding-window)
**Data structures:** Hash Table, String
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [Flipkart](https://scaleengineer.com/companies/flipkart), [Yandex](https://scaleengineer.com/companies/yandex), [Turing](https://scaleengineer.com/companies/turing), [PhonePe](https://scaleengineer.com/companies/phonepe), [UiPath](https://scaleengineer.com/companies/uipath), [Zepto](https://scaleengineer.com/companies/zepto), [MathWorks](https://scaleengineer.com/companies/mathworks), [Pocket Gems](https://scaleengineer.com/companies/pocket-gems), [PayU](https://scaleengineer.com/companies/payu)
---
## Problem
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 <= 105`
* `s` consists of only uppercase English letters.
* `0 <= k <= s.length`

# Approaches
## Brute Force with Optimization
This approach iterates through all possible substrings of the input string `s`. For each substring, it calculates the minimum number of replacements required to make all characters in it the same. If this number is within the allowed limit `k`, the length of the substring is considered as a potential answer. The maximum length found among all valid substrings is the result.
**Time:** O(N^2), where N is the length of the string `s`. The outer loop runs N times, and the inner loop runs up to N times. Inside the inner loop, operations are constant time. · **Space:** O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant.
**Pros:** Simple to understand and implement.; It's a direct translation of the problem statement.
**Cons:** Inefficient for large inputs. It will result in a 'Time Limit Exceeded' (TLE) error on platforms like LeetCode for the given constraints (N up to 10^5).
### Explanation
The naive brute-force approach would be to check every substring and for each substring, check against all 26 possible characters, leading to an O(n^3) complexity. We can optimize this.

A better brute-force method involves iterating through all possible start and end points of a substring, which is O(n^2). For each substring, we can determine the number of replacements needed more efficiently.

The number of replacements for a substring is its length minus the frequency of its most common character. To find this, we can maintain a frequency map for the characters within the current substring.

As we extend the substring by one character (by moving the end pointer), we update the frequency map and find the new most frequent character. This check takes constant time (O(1) since there are only 26 uppercase letters).

```java
class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int maxLength = 0;
        for (int i = 0; i < n; i++) {
            int[] charCounts = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                charCounts[s.charAt(j) - 'A']++;
                maxFreq = Math.max(maxFreq, charCounts[s.charAt(j) - 'A']);
                int replacementsNeeded = (j - i + 1) - maxFreq;
                if (replacementsNeeded <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `maxLength = 0`.
- Iterate through the string with a starting pointer `i` from 0 to `n-1`.
- For each `i`, start an inner loop with an ending pointer `j` from `i` to `n-1`.
- Maintain a frequency map (e.g., an array of size 26) for the characters in the substring `s[i..j]`.
- In the inner loop, as `j` increments, update the frequency of `s[j]`.
- Find the frequency of the most common character in the current substring `s[i..j]`, let's call it `maxFreq`.
- The number of replacements needed is `(j - i + 1) - maxFreq`.
- If `(j - i + 1) - maxFreq <= k`, then this substring is a candidate. Update `maxLength = max(maxLength, j - i + 1)`.
- After both loops complete, `maxLength` will hold the answer.

## Optimal Sliding Window
A much more efficient approach uses the sliding window technique. We maintain a 'window' (a substring) and expand it to the right. We keep track of the character frequencies within the window. If the window becomes 'invalid' (meaning it requires more than `k` replacements), we shrink it from the left until it's valid again. The maximum size the window reaches at any point is the answer.
**Time:** O(N), where N is the length of the string `s`. Both `right` and `left` pointers traverse the string at most once. The work inside the loop is constant time. · **Space:** O(1), as the frequency map `charCounts` has a fixed size of 26, which is constant regardless of the input string size.
**Pros:** Highly efficient with linear time complexity.; Optimal solution for this problem.; Effectively utilizes the properties of the problem to avoid redundant calculations.
**Cons:** The logic, especially the part about not needing to update `maxFreq` when shrinking the window, can be slightly non-intuitive at first glance.
### Explanation
The core idea is to find the longest substring (window) `s[left..right]` where the number of characters that are *not* the most frequent character is at most `k`.

This condition can be expressed as: `(window_length) - (frequency_of_most_common_char) <= k`.

We use two pointers, `left` and `right`, to define the current window. We iterate `right` from the beginning to the end of the string, expanding the window.

For each expansion, we update the frequency count of the new character `s[right]` and also keep track of `maxFreq`, the highest frequency of any single character seen so far in the window.

After expanding, we check if our window is valid using the condition `(right - left + 1) - maxFreq <= k`. If it's not (`> k`), it means we have too many characters that need replacement. To fix this, we must shrink the window by moving the `left` pointer to the right and decrementing the count of the character `s[left]`.

A key optimization is that we don't need to re-calculate `maxFreq` when we shrink the window. We are looking for the *longest* substring. The window size only increases when `right` moves, not when `left` moves. So, we can maintain the historical `maxFreq` and the window will only expand again when we find a new, longer valid substring (which might happen because `maxFreq` increases).

The length of the window `right - left + 1` is a candidate for the answer at each step, and we keep track of the maximum length seen.

```java
class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int[] charCounts = new int[26];
        int left = 0;
        int maxLength = 0;
        int maxFreq = 0;

        for (int right = 0; right < n; right++) {
            // Expand the window
            charCounts[s.charAt(right) - 'A']++;
            maxFreq = Math.max(maxFreq, charCounts[s.charAt(right) - 'A']);

            // Check if the window is valid
            // Number of characters to replace = windowLength - maxFreq
            int windowLength = right - left + 1;
            if (windowLength - maxFreq > k) {
                // Shrink the window from the left
                charCounts[s.charAt(left) - 'A']--;
                left++;
            }

            // The window size is a potential answer
            maxLength = Math.max(maxLength, right - left + 1);
        }
        return maxLength;
    }
}
```
### Algorithm
- Initialize `left = 0`, `maxLength = 0`, `maxFreq = 0`, and a frequency map `counts` (array of size 26).
- Iterate through the string with a pointer `right` from 0 to `n-1`.
- Increment the count for `s[right]` in the `counts` map.
- Update `maxFreq = max(maxFreq, count of s[right])`.
- Check if the current window is invalid: `(right - left + 1) - maxFreq > k`.
- If it is invalid, shrink the window from the left: decrement the count of `s[left]` and increment `left`.
- The window size `right - left + 1` is always the size of the current valid (or just-became-valid) window. The maximum size this window ever reaches is the answer. We update `maxLength = max(maxLength, right - left + 1)` in each iteration.
- Return `maxLength`.

# Solutions
### Java

```java
class Solution { public int characterReplacement ( String s , int k ) { int [] counter = new int [ 26 ]; int i = 0 ; int j = 0 ; for ( int maxCnt = 0 ; i < s . length (); ++ i ) { char c = s . charAt ( i ); ++ counter [ c - 'A' ]; maxCnt = Math . max ( maxCnt , counter [ c - 'A' ]); if ( i - j + 1 - maxCnt > k ) { -- counter [ s . charAt ( j ) - 'A' ]; ++ j ; } } return i - j ; } }
```

### CPP

```cpp
class Solution { public: int characterReplacement ( string s , int k ) { vector < int > counter ( 26 ); int i = 0 , j = 0 , maxCnt = 0 ; for ( char & c : s ) { ++ counter [ c - 'A' ]; maxCnt = max ( maxCnt , counter [ c - 'A' ]); if ( i - j + 1 > maxCnt + k ) { -- counter [ s [ j ] - 'A' ]; ++ j ; } ++ i ; } return i - j ; } };
```

### Python

```python
class Solution : def characterReplacement ( self , s : str , k : int ) -> int : counter = [ 0 ] * 26 i = j = maxCnt = 0 while i < len ( s ): counter [ ord ( s [ i ]) - ord ( 'A' )] += 1 maxCnt = max ( maxCnt , counter [ ord ( s [ i ]) - ord ( 'A' )]) if i - j + 1 > maxCnt + k : counter [ ord ( s [ j ]) - ord ( 'A' )] -= 1 j += 1 i += 1 return i - j
```