Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Longest Repeating Character Replacement

MEDIUMProblemSolveExternal Links

Description

You are given a string s consisting of uppercase English letters and an integer k. You may select any character in the string and change it to any other uppercase English character. You can perform this replacement operation at most k times.

After performing at most k replacements, return the length of the longest substring that contains only one distinct character.

In other words, find the longest contiguous block of identical characters you can create by changing at most k characters within it.

Examples

Example 1

Input: s = "ABAB", k = 2

Output: 4

Explanation: We can replace both 'A' characters with 'B' (or both 'B' characters with 'A') using our 2 allowed replacements. This transforms the entire string into "BBBB" (or "AAAA"), giving us a substring of length 4 where every character is the same.

Example 2

Input: s = "AABABBA", k = 1

Output: 4

Explanation: Consider the substring "AABA" (indices 0 to 3). It contains three 'A's and one 'B'. We only need to replace that one 'B' with 'A' to get "AAAA" — a run of 4 identical characters. No longer valid substring can be formed with just 1 replacement.

Example 3

Input: s = "AAAA", k = 0

Output: 4

Explanation: The string already consists of 4 identical characters. No replacements are needed, and the entire string is the answer.

Constraints

  • 1 ≤ s.length ≤ 10^5
  • s consists of only uppercase English letters
  • 0 ≤ k ≤ s.length

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is: consider every possible substring of s, and for each one, check whether it can be turned into a string of all-identical characters using at most k replacements.

How do we check a given substring? If a substring has length L and the most frequent character in it appears maxFreq times, then we need to replace L - maxFreq characters to make all characters the same. If L - maxFreq ≤ k, the substring is valid.

So the brute force plan is:

  • Try every starting index i
  • Try every ending index j ≥ i
  • Count character frequencies in s[i..j]
  • Find the maximum frequency
  • Check if (j - i + 1) - maxFreq ≤ k
  • Track the longest valid substring

Step-by-Step Explanation

Let's trace through with s = "AABABBA", k = 1:

Step 1: Start with i=0. We will extend j from 0 onward and count characters.

Step 2: Substring s[0..0] = "A". Freq: {A:1}. maxFreq=1. Replacements needed = 1-1 = 0 ≤ 1. Valid. Length=1.

Step 3: Substring s[0..1] = "AA". Freq: {A:2}. maxFreq=2. Replacements = 2-2 = 0 ≤ 1. Valid. Length=2.

Step 4: Substring s[0..2] = "AAB". Freq: {A:2, B:1}. maxFreq=2. Replacements = 3-2 = 1 ≤ 1. Valid. Length=3.

Step 5: Substring s[0..3] = "AABA". Freq: {A:3, B:1}. maxFreq=3. Replacements = 4-3 = 1 ≤ 1. Valid. Length=4.

Step 6: Substring s[0..4] = "AABAB". Freq: {A:3, B:2}. maxFreq=3. Replacements = 5-3 = 2 > 1. Invalid! We need 2 replacements but only have 1.

Step 7: Move to i=1. Repeat expanding j. Substring s[1..4] = "ABAB". Freq: {A:2, B:2}. maxFreq=2. Replacements = 4-2 = 2 > 1. Invalid.

Step 8: Continue for all starting positions. The longest valid substring found is length 4 (for example s[0..3] = "AABA").

Result: 4

Brute Force — Checking All Substrings — Watch how we examine every possible substring, count character frequencies, and check whether it can become all-identical with at most k replacements.

Algorithm

  1. Initialize max_length = 0
  2. For each starting index i from 0 to n-1:
    a. Create a frequency count array of size 26 (for uppercase letters)
    b. For each ending index j from i to n-1:
    • Increment the count for character s[j]
    • Compute maxFreq = maximum value in the frequency array
    • Compute replacements = (j - i + 1) - maxFreq
    • If replacements ≤ k, update max_length = max(max_length, j - i + 1)
  3. Return max_length

Code

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        int maxLength = 0;
        
        for (int i = 0; i < n; i++) {
            int freq[26] = {0};
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                freq[s[j] - 'A']++;
                maxFreq = max(maxFreq, freq[s[j] - 'A']);
                int replacements = (j - i + 1) - maxFreq;
                if (replacements <= k) {
                    maxLength = max(maxLength, j - i + 1);
                }
            }
        }
        
        return maxLength;
    }
};
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        max_length = 0
        
        for i in range(n):
            freq = {}
            max_freq = 0
            for j in range(i, n):
                freq[s[j]] = freq.get(s[j], 0) + 1
                max_freq = max(max_freq, freq[s[j]])
                replacements = (j - i + 1) - max_freq
                if replacements <= k:
                    max_length = max(max_length, j - i + 1)
        
        return max_length
class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int maxLength = 0;
        
        for (int i = 0; i < n; i++) {
            int[] freq = new int[26];
            int maxFreq = 0;
            for (int j = i; j < n; j++) {
                freq[s.charAt(j) - 'A']++;
                maxFreq = Math.max(maxFreq, freq[s.charAt(j) - 'A']);
                int replacements = (j - i + 1) - maxFreq;
                if (replacements <= k) {
                    maxLength = Math.max(maxLength, j - i + 1);
                }
            }
        }
        
        return maxLength;
    }
}

Complexity Analysis

Time Complexity: O(n² × 26) ≈ O(n²)

We have two nested loops iterating over all possible substrings — the outer loop runs n times and the inner loop runs up to n times for each outer iteration. For each substring, finding maxFreq costs O(26) if we scan the frequency array, but since we update it incrementally, each inner iteration is O(1). Overall: O(n²).

Space Complexity: O(26) = O(1)

We use a fixed-size frequency array of 26 characters. This does not grow with input size, so the space complexity is constant.

Why This Approach Is Not Efficient

The brute force approach examines O(n²) substrings. With n up to 10^5, that means up to 5 × 10^9 operations — far too slow for typical competitive programming time limits (usually around 10^8 operations per second).

The core inefficiency is that when we find a substring that requires too many replacements (i.e., it becomes invalid), we don't use that information intelligently. We simply move i forward by one and repeat the entire inner scan. We're throwing away knowledge about the window's character distribution.

The key insight is: if a window of size L starting at i is valid, we don't need to check smaller windows starting at i. And if a window becomes invalid, we can shrink it from the left rather than restarting. This is the sliding window pattern — we can maintain a window that only grows or slides, never restarts from scratch.

Optimal Approach - Sliding Window

Intuition

Instead of checking every substring, we maintain a window defined by two pointers — left and right. We expand the window by moving right forward, and we shrink it by moving left forward when the window becomes invalid.

The validity condition is the same as before: for a window of size windowSize where the most frequent character appears maxFreq times, we need windowSize - maxFreq replacements. If this exceeds k, the window is invalid.

Here is the clever part: when the window becomes invalid, we only shrink it by one position (move left forward by one). We don't shrink it all the way down to a valid state. Why? Because we're searching for the longest valid window. Once we've found a valid window of size W, we're only interested in windows of size W + 1 or larger. By maintaining the window size and sliding it forward, we're effectively searching for something better than what we've already found.

Another subtlety: we track maxFreq as the highest frequency we've ever seen in any window — not necessarily the exact maximum in the current window. This is safe because maxFreq only helps the window grow. If the current window's true maximum is lower, the window simply won't grow (it stays the same size or slides), which is the correct behavior since we can't beat our previous best anyway.

Think of it like moving a measuring ruler along a wall: the ruler can grow longer when we find good spots, but it never shrinks smaller than its best length. We slide it forward looking for an even better spot.

Step-by-Step Explanation

Let's trace through with s = "AABABBA", k = 1:

Step 1: Initialize: left=0, maxFreq=0, freq={}, max_length=0.

Step 2: right=0, char='A'. freq={'A':1}. maxFreq = max(0,1) = 1. Window="A", size=1. Replacements = 1-1 = 0 ≤ 1. Valid. Window stays.

Step 3: right=1, char='A'. freq={'A':2}. maxFreq = max(1,2) = 2. Window="AA", size=2. Replacements = 2-2 = 0 ≤ 1. Valid.

Step 4: right=2, char='B'. freq={'A':2,'B':1}. maxFreq = max(2,1) = 2. Window="AAB", size=3. Replacements = 3-2 = 1 ≤ 1. Valid.

Step 5: right=3, char='A'. freq={'A':3,'B':1}. maxFreq = max(2,3) = 3. Window="AABA", size=4. Replacements = 4-3 = 1 ≤ 1. Valid.

Step 6: right=4, char='B'. freq={'A':3,'B':2}. maxFreq = max(3,2) = 3. Window="AABAB", size=5. Replacements = 5-3 = 2 > 1. Invalid! Shrink: remove s[0]='A', freq={'A':2,'B':2}, left=1. Window="ABAB", size=4.

Step 7: right=5, char='B'. freq={'A':2,'B':3}. maxFreq = max(3,3) = 3. Window="ABABB", size=5. Replacements = 5-3 = 2 > 1. Invalid! Shrink: remove s[1]='A', freq={'A':1,'B':3}, left=2. Window="BABB", size=4.

Step 8: right=6, char='A'. freq={'A':2,'B':3}. maxFreq = max(3,2) = 3. Window="BABBA", size=5. Replacements = 5-3 = 2 > 1. Invalid! Shrink: remove s[2]='B', freq={'A':2,'B':2}, left=3. Window="ABBA", size=4.

Step 9: All characters processed. Answer = len(s) - left = 7 - 3 = 4.

Result: 4

Sliding Window — Expanding and Shrinking for Longest Valid Substring — Watch how the sliding window expands when the substring is valid and slides forward (shrinks by one from left) when too many replacements are needed.

Algorithm

  1. Initialize left = 0, maxFreq = 0, and a frequency map freq (size 26)
  2. For each right from 0 to n-1:
    a. Increment freq[s[right]]
    b. Update maxFreq = max(maxFreq, freq[s[right]])
    c. If window is invalid (right - left + 1 - maxFreq > k):
    • Decrement freq[s[left]]
    • Increment left
  3. Return n - left (the size of the final window position)

Code

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        int freq[26] = {0};
        int left = 0;
        int maxFreq = 0;
        
        for (int right = 0; right < n; right++) {
            freq[s[right] - 'A']++;
            maxFreq = max(maxFreq, freq[s[right] - 'A']);
            
            if (right - left + 1 - maxFreq > k) {
                freq[s[left] - 'A']--;
                left++;
            }
        }
        
        return n - left;
    }
};
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        freq = {}
        left = 0
        max_freq = 0
        
        for right in range(n):
            freq[s[right]] = freq.get(s[right], 0) + 1
            max_freq = max(max_freq, freq[s[right]])
            
            if right - left + 1 - max_freq > k:
                freq[s[left]] -= 1
                left += 1
        
        return n - left
class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        int[] freq = new int[26];
        int left = 0;
        int maxFreq = 0;
        
        for (int right = 0; right < n; right++) {
            freq[s.charAt(right) - 'A']++;
            maxFreq = Math.max(maxFreq, freq[s.charAt(right) - 'A']);
            
            if (right - left + 1 - maxFreq > k) {
                freq[s.charAt(left) - 'A']--;
                left++;
            }
        }
        
        return n - left;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the string once with the right pointer, and the left pointer also moves at most n times total. Each character is added and removed from the frequency map at most once. All operations inside the loop (frequency update, max comparison, validity check) are O(1). The total work is O(n).

Space Complexity: O(1)

The frequency map stores counts for at most 26 uppercase English letters. This is a fixed size regardless of input length, making space complexity O(26) = O(1).