Character Replacement — Problem Statement & Solution Guide

Sliding WindowMediumSliding Window / Frequency Map

TimeO(n)

SpaceO(1)

Problem Description

Given a string s consisting of uppercase English letters and an integer k, determine the length of the longest contiguous substring that can be transformed into a string of identical characters by changing at most k characters. The transformation allows replacing any character in the substring with any other uppercase letter. Your goal is to find the maximum window size where the number of non-dominant characters does not exceed k.

The input consists of a single string s and an integer k. The output should be a single integer representing the length of the longest valid substring. If the string is empty, return 0. The solution must efficiently handle large input sizes by leveraging the properties of sliding windows and frequency counting.

DSA Pattern Breakdown

"Character Replacement"

medium

WHY DOES IT MATTER?

Sliding‑window is a fundamental pattern for problems that ask for optimal subarrays or substrings under a constraint. It transforms a potentially quadratic search into linear time by reusing work from previous window positions, which is crucial for handling large inputs in real‑time systems.

OPTIMIZATION CHALLENGE

The breakthrough is recognizing that only the count of the most frequent character matters. By maintaining a running maxFreq, we avoid recomputing the full frequency distribution on each shrink, collapsing the naive O(26·n) updates to O(1) per step.

REAL-WORLD CONNECTION

Think of a network packet buffer that can tolerate up to k corrupted bits. As packets stream in, you want the longest contiguous segment that can be corrected with limited error‑correction resources. The sliding window mirrors how the buffer expands until the error budget is exceeded, then discards the oldest packet to stay within limits.

During an interview, keep the window invariant clear: "the window is valid if we can turn it into a uniform string with ≤ k changes". Update the frequency map and maxFreq as you move the right pointer, and only move the left pointer when the invariant breaks. This mental model prevents off‑by‑one errors.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The problem asks for the longest substring that can be turned into a same‑character string with at most k replacements. A naive scan that checks every possible window would be O(n²) because for each start index you would expand the end index and count the most frequent character inside the window. This quickly becomes infeasible for strings of length up to 10⁵, which is typical in interview constraints.

The optimal solution leverages the sliding‑window (two‑pointer) technique combined with a frequency map of the 26 uppercase letters. While expanding the right pointer, we keep track of the count of the most frequent character in the current window (maxFreq). The window is valid as long as its length minus maxFreq ≤ k, i.e., the number of characters that need to be changed does not exceed the allowed budget. If the condition breaks, we shrink the left side of the window, updating the frequency map accordingly. Because each character is visited at most twice (once by the right pointer, once by the left), the overall time is linear.

The key insight is that we do not need the exact distribution of all characters; only the count of the most frequent one matters. This allows us to avoid recomputing the max frequency from scratch on every shrink operation—maintaining a running maxFreq suffices, even though it may be slightly stale, because the window size only grows when the condition holds. This yields an O(n) time and O(1) space algorithm, which is optimal for this class of problems.

Interview Questions on This Problem

Q1How would you modify the solution if the string could contain both uppercase and lowercase letters (52 possible characters)?

The algorithm remains unchanged; you just need a frequency array of size 52 (or a hashmap) instead of 26. The sliding‑window logic still tracks the most frequent character count, and the time/space complexities stay O(n) and O(1) respectively because the alphabet size is constant.

Q2Can you adapt the approach to return the actual substring(s) achieving the maximum length, not just the length?

Yes. While sliding the window, keep track of the start index whenever a new maximum length is found. After the scan, you can slice the original string from that start index for the recorded max length. If multiple substrings share the maximum length, store all start indices in a list.

Q3Explain how the sliding‑window technique for this problem relates to the "minimum window substring" problem and what key difference changes the algorithmic focus.

Both problems use two pointers to maintain a dynamic window and a frequency map. In the minimum window substring, the goal is to shrink the window until it just satisfies a requirement, then try to minimize its size. Here, we expand the window as long as the replacement budget permits and only shrink when the budget is exceeded, aiming to maximize size. Thus, the condition check (window size - maxFreq ≤ k) drives expansion rather than contraction.

Examples

Example 1

Input

s = "AABABBA", k = 1

Output

Explanation: Consider the substring "ABBA" (indices 2 to 5). The frequency of 'B' is 3 and 'A' is 1. To make all characters 'B', we need to change 1 'A' to 'B'. Since k=1, this is valid. The length is 4. Other windows like "AABA" require 2 changes (invalid). The maximum length found is 4.

Example 2

Input

s = "ABAB", k = 2

Output

Explanation: The entire string "ABAB" has frequencies: A=2, B=2. The maximum frequency is 2. The number of changes required to make all characters the same is 4 - 2 = 2. Since k=2, the entire string is valid. The length is 4.

Example 3

Input

s = "AAABBB", k = 0

Output

Explanation: With k=0, no changes are allowed. We must find the longest substring that already consists of identical characters. The substrings "AAA" and "BBB" both have length 3. Any longer substring contains mixed characters and would require changes. Thus, the answer is 3.

Example 4

Input

s = "CBAAC", k = 1

Output

Explanation: Check window "CBA" (len 3): max freq 1, changes needed 2 (invalid). Window "BAA" (len 3): max freq 2 ('A'), changes needed 1 (valid). Window "AAC" (len 3): max freq 2 ('A'), changes needed 1 (valid). Window "CBAAC" (len 5): max freq 2 ('A'), changes needed 3 (invalid). The maximum valid length is 3.

Constraints

1 <= s.length <= 10^5
0 <= k <= s.length
s consists of uppercase English letters only

Optimal Approach & Strategy

Use a sliding window with a 26‑size frequency array, maintain the current max frequency, and adjust the left pointer only when the window violates the replacement budget.

Brute Force Approach

Check every possible substring, count the most frequent character inside it, and verify if length‑maxFreq ≤ k; keep the maximum length found.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    const n = s.length;
    if (n === 0) return 0;
    
    const freq = new Array(26).fill(0);
    let maxFreq = 0;
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < n; right++) {
        freq[s.charCodeAt(right) - 'A'.charCodeAt(0)]++;
        maxFreq = Math.max(maxFreq, freq[s.charCodeAt(right) - 'A'.charCodeAt(0)]);
        
        if (right - left + 1 - maxFreq > k) {
            freq[s.charCodeAt(left) - 'A'.charCodeAt(0)]--;
            left++;
        }
        
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
};

class Solution {
public:
    int characterReplacement(string s, int k) {
        int n = s.size();
        if (n == 0) return 0;
        
        vector<int> freq(26, 0);
        int maxFreq = 0;
        int left = 0;
        int maxLength = 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++;
            }
            
            maxLength = max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
};

class Solution {
    public int characterReplacement(String s, int k) {
        int n = s.length();
        if (n == 0) return 0;
        
        int[] freq = new int[26];
        int maxFreq = 0;
        int left = 0;
        int maxLength = 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++;
            }
            
            maxLength = Math.max(maxLength, right - left + 1);
        }
        
        return maxLength;
    }
}

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        n = len(s)
        if n == 0:
            return 0
        
        freq = [0] * 26
        max_freq = 0
        left = 0
        max_length = 0
        
        for right in range(n):
            freq[ord(s[right]) - ord('A')] += 1
            max_freq = max(max_freq, freq[ord(s[right]) - ord('A')])
            
            if right - left + 1 - max_freq > k:
                freq[ord(s[left]) - ord('A')] -= 1
                left += 1
            
            max_length = max(max_length, right - left + 1)
        
        return max_length

/**
 * @param {string} s
 * @param {number} k
 * @return {number}
 */
var characterReplacement = function(s, k) {
    const n = s.length;
    if (n === 0) return 0;
    
    const freq = new Array(26).fill(0);
    let maxFreq = 0;
    let left = 0;
    let maxLength = 0;
    
    for (let right = 0; right < n; right++) {
        freq[s.charCodeAt(right) - 'A'.charCodeAt(0)]++;
        maxFreq = Math.max(maxFreq, freq[s.charCodeAt(right) - 'A'.charCodeAt(0)]);
        
        if (right - left + 1 - maxFreq > k) {
            freq[s.charCodeAt(left) - 'A'.charCodeAt(0)]--;
            left++;
        }
        
        maxLength = Math.max(maxLength, right - left + 1);
    }
    
    return maxLength;
};

Asked in Top Tech Interviews

Uber

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Character Replacement Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Sliding Window

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Character Replacement — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Asked in Top Tech Interviews

Solve in Interative Editor