What happens if you not updating max frequency correctly when shrinking window?

Window shrinks incorrectly or max frequency is stale, leading to wrong answer Fix: Do not decrease max frequency when shrinking; keep track of max frequency as max so far

What happens if you using a hashmap without considering character set size?

Unnecessary overhead and slower performance Fix: Use fixed-size array for uppercase letters to improve speed

What happens if you shrinking window too early or too late?

Window size is incorrect, resulting in wrong max length Fix: Shrink window only when replacements needed exceed k

What happens if you not handling edge cases like k=0 or single character strings?

Incorrect output or runtime errors Fix: Test and handle minimal and boundary inputs explicitly

Interview Prepsliding-windowmediumAmazonGoogleBloomberg

Longest Repeating Character Replacement

Choose your preparation mode4 modes available

Try It Solution Trace

🎯

mediumSLIDING_WINDOWAmazonGoogleBloomberg

Imagine you are editing a text and want to find the longest segment where you can replace a few characters to make all characters identical, helping you optimize formatting or compression.

💡 This problem is a classic example of using a sliding window with variable size. Beginners often struggle because they try fixed window sizes or brute force all substrings, missing the insight that the window can expand and shrink dynamically based on character frequency constraints.

📋

Problem Statement

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 at most k times. Return the length of the longest substring containing the same letter you can get after performing the above operations.

1 ≤ s.length ≤ 10^5s consists of only uppercase English letters0 ≤ k ≤ s.length

💡

Example

Input"s = \"ABAB\", k = 2"

Output4

Replace two 'A's with 'B's or vice versa to get "BBBB" or "AAAA".

Input"s = \"AABABBA\", k = 1"

Output4

Replace one 'B' in the substring "ABAB" to get "AAAA" or "BBBB".

All characters are the same and k = 0 → output is length of string
k = 0 and string has all distinct characters → output is 1
k equals string length → output is string length
String length = 1 → output is 1

⚠️

Common Mistakes

Not updating max frequency correctly when shrinking window

Window shrinks incorrectly or max frequency is stale, leading to wrong answer

✅ Do not decrease max frequency when shrinking; keep track of max frequency as max so far

Using a hashmap without considering character set size

Unnecessary overhead and slower performance

✅ Use fixed-size array for uppercase letters to improve speed

Shrinking window too early or too late

Window size is incorrect, resulting in wrong max length

✅ Shrink window only when replacements needed exceed k

Not handling edge cases like k=0 or single character strings

Incorrect output or runtime errors

✅ Test and handle minimal and boundary inputs explicitly

🧠

Brute Force (Check All Substrings)

💡 Starting with brute force helps understand the problem deeply by considering all possible substrings and checking if they can be converted with at most k replacements. It’s inefficient but builds intuition.

Intuition

Try every substring, count the frequency of each character, and check if the substring can be made uniform by replacing at most k characters.

Algorithm

Enumerate all substrings of s using two nested loops.
For each substring, count the frequency of each character.
Calculate the number of replacements needed as substring length minus max frequency.
If replacements needed ≤ k, update the maximum length found.

💡 The nested loops and frequency counting make this approach straightforward but slow, which is why it’s a good starting point to understand the problem.

</>

Code

def characterReplacement(s: str, k: int) -> int:
    max_len = 0
    n = len(s)
    for start in range(n):
        freq = {}
        max_count = 0
        for end in range(start, n):
            freq[s[end]] = freq.get(s[end], 0) + 1
            max_count = max(max_count, freq[s[end]])
            if (end - start + 1) - max_count <= k:
                max_len = max(max_len, end - start + 1)
    return max_len

# Driver code
if __name__ == '__main__':
    print(characterReplacement("ABAB", 2))  # Expected output: 4

Line Notes

for start in range(n):Outer loop picks the start index of substring

freq = {}Reset frequency dictionary for each new start

for end in range(start, n):Inner loop picks the end index of substring

freq[s[end]] = freq.get(s[end], 0) + 1Count frequency of current character in substring

max_count = max(max_count, freq[s[end]])Track the most frequent character count in substring

if (end - start + 1) - max_count <= k:Check if replacements needed are within k

max_len = max(max_len, end - start + 1)Update max length if condition satisfied

import java.util.*;
public class Solution {
    public int characterReplacement(String s, int k) {
        int maxLen = 0;
        int n = s.length();
        for (int start = 0; start < n; start++) {
            Map<Character, Integer> freq = new HashMap<>();
            int maxCount = 0;
            for (int end = start; end < n; end++) {
                char c = s.charAt(end);
                freq.put(c, freq.getOrDefault(c, 0) + 1);
                maxCount = Math.max(maxCount, freq.get(c));
                if ((end - start + 1) - maxCount <= k) {
                    maxLen = Math.max(maxLen, end - start + 1);
                }
            }
        }
        return maxLen;
    }
    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.characterReplacement("ABAB", 2)); // Expected output: 4
    }
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop selects substring start

Map<Character, Integer> freq = new HashMap<>();Frequency map reset for each start

for (int end = start; end < n; end++) {Inner loop selects substring end

freq.put(c, freq.getOrDefault(c, 0) + 1);Update frequency of current character

maxCount = Math.max(maxCount, freq.get(c));Track max frequency in current substring

if ((end - start + 1) - maxCount <= k) {Check if replacements needed are within k

maxLen = Math.max(maxLen, end - start + 1);Update max length if valid

#include <iostream>
#include <unordered_map>
#include <string>
using namespace std;

int characterReplacement(string s, int k) {
    int maxLen = 0;
    int n = s.size();
    for (int start = 0; start < n; start++) {
        unordered_map<char, int> freq;
        int maxCount = 0;
        for (int end = start; end < n; end++) {
            freq[s[end]]++;
            maxCount = max(maxCount, freq[s[end]]);
            if ((end - start + 1) - maxCount <= k) {
                maxLen = max(maxLen, end - start + 1);
            }
        }
    }
    return maxLen;
}

int main() {
    cout << characterReplacement("ABAB", 2) << endl; // Expected output: 4
    return 0;
}

Line Notes

for (int start = 0; start < n; start++) {Outer loop for substring start index

unordered_map<char, int> freq;Frequency map reset for each start

for (int end = start; end < n; end++) {Inner loop for substring end index

freq[s[end]]++;Increment frequency of current character

maxCount = max(maxCount, freq[s[end]]);Track max frequency in substring

if ((end - start + 1) - maxCount <= k) {Check if replacements needed are within k

maxLen = max(maxLen, end - start + 1);Update max length if condition met

function characterReplacement(s, k) {
    let maxLen = 0;
    const n = s.length;
    for (let start = 0; start < n; start++) {
        const freq = {};
        let maxCount = 0;
        for (let end = start; end < n; end++) {
            freq[s[end]] = (freq[s[end]] || 0) + 1;
            maxCount = Math.max(maxCount, freq[s[end]]);
            if ((end - start + 1) - maxCount <= k) {
                maxLen = Math.max(maxLen, end - start + 1);
            }
        }
    }
    return maxLen;
}

// Driver code
console.log(characterReplacement("ABAB", 2)); // Expected output: 4

Line Notes

for (let start = 0; start < n; start++) {Outer loop selects substring start

const freq = {};Reset frequency object for each start

for (let end = start; end < n; end++) {Inner loop selects substring end

freq[s[end]] = (freq[s[end]] || 0) + 1;Update frequency of current character

maxCount = Math.max(maxCount, freq[s[end]]);Track max frequency in substring

if ((end - start + 1) - maxCount <= k) {Check if replacements needed are within k

maxLen = Math.max(maxLen, end - start + 1);Update max length if valid

⏱

Complexity

TimeO(n^2)

SpaceO(n)

Two nested loops generate O(n^2) substrings, and frequency counting inside inner loop is O(1) amortized using hashmap. Overall O(n^2).

💡 For n=20, this means about 400 substring checks, which is manageable, but for n=10^5 it becomes impractical.

Interview Verdict: TLE

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	`O(n^2)`	`O(n)`	No	N/A	Mention only - never code due to inefficiency
2. Sliding Window with HashMap	`O(n)`	`O(1)`	No	N/A	Code this if input alphabet is unknown or large
3. Sliding Window with Frequency Array	`O(n)`	`O(1)`	No	N/A	Preferred approach for uppercase letters due to simplicity and speed

Practice

(1/5)

1. You are given a binary array and an integer k. You want to find the length of the longest contiguous subarray containing only 1s after flipping at most k zeros to 1s. Which algorithmic approach guarantees an optimal solution with linear time complexity?

easy

A. Sliding window with two pointers maintaining a window that contains at most k zeros

B. Brute force nested loops checking all subarrays and counting zeros each time

C. Dynamic programming with memoization over subarray indices and zero counts

D. Greedy approach flipping zeros as soon as encountered without shrinking window

3. The following code attempts to count the number of subarrays with at most k odd numbers using a sliding window. Identify the line containing the subtle bug that causes incorrect results or inefficiency.

def countAtMost(nums, k):
    count = 0
    left = 0
    odd_count = 0
    for right in range(len(nums)):
        if nums[right] % 2 == 1:
            odd_count += 1
        while odd_count > k:
            if nums[left] % 2 == 1:
                odd_count -= 1
            left += 1
        count += right - left
    return count

medium

A. Line 14: count += right - left

B. Line 10: while odd_count > k:

C. Line 12: left += 1

D. Line 6: if nums[right] % 2 == 1: odd_count += 1

Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard

Intuition

Algorithm

Intuition

Algorithm

Intuition

Algorithm

How to Present

Time Allocation

What the Interviewer Tests

Common Follow-ups

When to Use

Signature Phrases

NOT This Pattern When

Similar Problems

Practice

Solution

Step 1: Understand problem constraints

Step 2: Identify suitable algorithm

Final Answer:

Quick Check:

Solution

Step 1: Understand problem constraints

Step 2: Identify optimal approach

Final Answer:

Quick Check:

Solution

Step 1: Understand counting formula

Step 2: Identify off-by-one error

Final Answer:

Quick Check:

Solution

Step 1: Identify main loop operations

Step 2: Check frequency updates and comparisons

Final Answer:

Quick Check:

Solution

Step 1: Identify loop behavior

Step 2: Analyze queue operations and pointer moves

Final Answer:

Quick Check:

Ready to prove it?