Longest Repeating Character Replacement

📋

Longest Repeating Character Replacement

Edge cases:

</>

IDE

def characterReplacement(s: str, k: int) -> int:public int characterReplacement(String s, int k)int characterReplacement(string s, int k)function characterReplacement(s, k)

def characterReplacement(s: str, k: int) -> int:
    # Write your solution here
    pass

class Solution {
    public int characterReplacement(String s, int k) {
        // Write your solution here
        return 0;
    }
}

#include <string>
using namespace std;

int characterReplacement(string s, int k) {
    // Write your solution here
    return 0;
}

function characterReplacement(s, k) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 0Fails to handle empty string input, returns default 0 or crashes.✅ Add base case: if s is empty, return 0 immediately.

Wrong: length of s - 1Off-by-one error in window length calculation (using end - start instead of end - start + 1).✅ Calculate window length as (end - start + 1) consistently.

Wrong: greater than allowed replacementsNot shrinking window when replacements needed exceed k, or miscalculating max frequency.✅ Shrink window when (window length - max frequency) > k; update max frequency dynamically.

Wrong: incorrect max length for alternating charsGreedy approach using global max frequency instead of window max frequency.✅ Track max frequency only within current window, update as window slides.

Wrong: TLEUsing brute force O(n^2) approach on large input.✅ Implement O(n) sliding window with frequency map and max count tracking.

✓

Test Cases

Focus on handling minimal and boundary inputs correctly to avoid crashes or incorrect results.

Analyze your algorithm for common pitfalls like greedy traps and off-by-one errors.

Optimize your solution to linear time complexity to handle large inputs efficiently.

t1_01basic

Input{"s":"ABAB","k":2}

Expected4

⏱ Performance - must finish in 2000ms

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

💡 Consider using a sliding window to track the longest valid substring.

💡 Track the count of the most frequent character in the current window.

💡 Expand window while (window length - max frequency) <= k; else shrink window.

Why it failed: Incorrect output means the window size or max frequency tracking is wrong. Fix by updating max frequency correctly and adjusting window size accordingly.

✓ Correctly handles the canonical example with replacements.

t1_02basic

Input{"s":"AABABBA","k":1}

Expected4

⏱ Performance - must finish in 2000ms

Replace one 'A' with 'B' in substring "ABBA" to get "BBBB" or "AAAA", max length 4.

💡 Use a sliding window and frequency map to track character counts.

💡 Maintain max frequency character count to decide if window is valid.

💡 Shrink window when replacements needed exceed k.

Why it failed: If output is less than 4, likely not shrinking window properly or not updating max frequency correctly. Fix by recalculating max frequency or adjusting window boundaries.

✓ Correctly finds max substring length with one replacement.

t2_01edge

Input{"s":"","k":0}

Expected0

⏱ Performance - must finish in 2000ms

Empty string input returns 0 as no substring exists.

💡 Check how your code handles empty input strings.

💡 Ensure no index out of bounds or invalid window operations occur.

💡 Return 0 immediately if string length is zero.

Why it failed: Code crashes or returns non-zero for empty string. Fix by adding a base case to return 0 if s is empty.

✓ Handles empty string input gracefully.

t2_02edge

Input{"s":"A","k":0}

Expected1

⏱ Performance - must finish in 2000ms

Single character string with zero replacements returns length 1.

💡 Test minimal input size with no replacements allowed.

💡 Window should handle single character correctly.

💡 Return length 1 since single char is already uniform.

Why it failed: Returns 0 or errors on single character input. Fix by ensuring window initialization and max frequency logic handle single element.

✓ Correctly returns 1 for single character string.

t2_03edge

Input{"s":"ABCDE","k":0}

Expected1

⏱ Performance - must finish in 2000ms

No replacements allowed and all distinct characters means max substring length is 1.

💡 When k=0, only substrings with identical chars count.

💡 Check if your code handles zero replacement constraint correctly.

💡 Max frequency in window must equal window size to be valid.

Why it failed: Returns >1 when k=0 and all chars distinct. Fix by ensuring window shrinks when replacements needed > k.

✓ Correctly returns 1 when no replacements allowed and all chars distinct.

t2_04edge

Input{"s":"AAAAA","k":0}

Expected5

⏱ Performance - must finish in 2000ms

All characters same and zero replacements allowed means max substring is entire string.

💡 Check if your code handles all identical characters correctly.

💡 Max frequency should be equal to window size for entire string.

💡 No shrinking needed when replacements needed is zero.

Why it failed: Returns less than full length for all identical chars with k=0. Fix by correctly tracking max frequency and window size.

✓ Correctly returns full length for identical chars with zero replacements.

t3_01corner

Input{"s":"AABBBCCDDDD","k":2}

Expected6

⏱ Performance - must finish in 2000ms

Longest substring after replacing up to 2 chars is length 7 (e.g. "BBBBCC" or "CCDDDD" with replacements).

💡 Beware of greedy approach that always picks max frequency char globally.

💡 Sliding window must track max frequency in current window, not entire string.

💡 Update max frequency dynamically as window slides.

Why it failed: Fails if max frequency is computed globally, not per window. Fix by tracking max frequency within current window only.

✓ Correctly handles dynamic max frequency per window.

t3_02corner

Input{"s":"ABABABABAB","k":3}

Expected7

⏱ Performance - must finish in 2000ms

Replacing 3 chars in alternating pattern yields max substring length 7.

💡 Check if your solution mistakenly treats problem as unbounded replacements.

💡 Remember k is max replacements allowed, not unlimited.

💡 Ensure window shrinks when replacements needed exceed k.

Why it failed: Fails if code assumes unlimited replacements or unbounded knapsack analogy. Fix by enforcing replacement count <= k.

✓ Correctly respects replacement limit k.

t3_03corner

Input{"s":"AABACCAAA","k":2}

Expected6

⏱ Performance - must finish in 2000ms

Longest substring length 7 after replacing 2 chars (e.g. "ACCAAA" to "AAAAAAA").

💡 Watch for off-by-one errors in window size calculation.

💡 Ensure window length is end - start + 1, not end - start.

💡 Update max length after adjusting window boundaries.

Why it failed: Returns length off by one due to incorrect window size calculation. Fix by using (end - start + 1) for window length.

✓ Correctly calculates window length.

t4_01performance

Input{"s":"AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAABBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB","k":10000}

Expectednull

⏱ Performance - must finish in 2000ms

n=100,000, O(n) sliding window solution must complete within 2 seconds.

💡 Brute force O(n^2) will time out on large input.

💡 Use sliding window with frequency map and max count tracking for O(n).

💡 Avoid recomputing max frequency from scratch each step.

Why it failed: TLE due to O(n^2) brute force approach. Fix by implementing O(n) sliding window with frequency counts.

✓ Efficient O(n) solution passes performance test.

Practice

1. You are given an array representing types of fruits in a row of trees. You want to collect fruits by choosing a contiguous segment of trees such that you only pick fruits of at most two different types. Which algorithmic approach guarantees finding the longest such segment efficiently?

easy

A. Sorting the array and then using two pointers to find longest subarray with two distinct values

B. Greedy approach that picks fruits until a third type appears, then restarts from the next tree

C. Dynamic programming to store longest segments ending at each index with at most two fruit types

D. Sliding window with a hash map to track counts of fruit types and dynamically adjust window size

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the longest contiguous subarray with at most two distinct fruit types.

2. Step 2: Identify suitable algorithm

   Sliding window with a hash map efficiently tracks counts of fruit types in the current window and adjusts window size when more than two types appear, ensuring O(n) time.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window with hashmap is classic for variable-size window problems [OK]

Hint: Sliding window with hashmap tracks counts dynamically [OK]

Common Mistakes:

• Assuming greedy restart always works
• Using DP unnecessarily
• Sorting breaks contiguous constraint

2. You manage a bookstore where customers arrive each minute, but the owner sometimes gets grumpy and ignores customers during certain minutes. You can choose a continuous time window of fixed length to calm the owner, making them satisfied during that window. Which algorithmic approach guarantees finding the maximum total satisfied customers?

easy

A. Sliding window to find the window maximizing extra satisfied customers plus base satisfaction

B. Dynamic programming over all subsets of minutes to maximize satisfaction

C. Greedy approach selecting the largest single minute with grumpy customers

D. Sorting customers by count and picking top X minutes regardless of continuity

Solution

1. Step 1: Understand problem constraints

   The problem requires selecting a continuous window of fixed length to maximize extra satisfaction, so continuity matters.

2. Step 2: Identify suitable algorithm

   Sliding window efficiently finds the maximum sum of grumpy customers in any continuous window, combined with base satisfaction from non-grumpy minutes.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window handles continuous windows optimally [OK]

Hint: Continuous window optimization -> sliding window [OK]

Common Mistakes:

• Thinking greedy picking largest single minute suffices
• Ignoring continuity of window
• Trying DP over subsets unnecessarily

3. You are given an array of positive integers and a target sum. You need to find the length of the smallest contiguous subarray whose sum is at least the target. Which algorithmic approach guarantees an optimal O(n) time solution for this problem?

easy

A. Brute force nested loops checking all subarrays

B. Sorting the array and using binary search for subarray sums

C. Dynamic programming with memoization over subarray sums

D. Sliding window with two pointers adjusting window size dynamically

Solution

1. Step 1: Understand problem constraints

   The problem requires finding the minimal length subarray with sum ≥ target, which suggests a variable-size window approach.

2. Step 2: Identify algorithm that adjusts window size efficiently

   Sliding window with two pointers can expand and shrink the window in O(n) time, ensuring minimal length is found without checking all subarrays.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window is known for O(n) minimal subarray sum solutions [OK]

Hint: Minimal subarray sum -> variable-size sliding window [OK]

Common Mistakes:

• Thinking sorting helps with contiguous subarrays
• Assuming DP is needed for minimal length
• Using brute force for optimality

4. You are given two strings s and t. Your task is to find the shortest substring in s that contains all characters of t including duplicates. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Dynamic programming to build a table of minimum substrings for all prefixes of s and t

B. Greedy approach that expands the window until all characters are found, then shrinks it from the left without tracking counts

C. Sliding window with two pointers and frequency maps to track counts of characters in the current window

D. Sorting both strings and using two pointers to find matching characters in order

Solution

1. Step 1: Understand problem requirements

   The problem requires finding the shortest substring containing all characters of t with correct counts, which demands tracking character frequencies.

2. Step 2: Evaluate algorithm suitability

   Greedy without frequency tracking can miss duplicates; DP is inefficient and not straightforward here; sorting breaks substring order. Sliding window with frequency maps efficiently tracks counts and adjusts window size optimally.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Sliding window with frequency maps is the classic optimal approach [OK]

Hint: Track counts with two pointers for optimal substring [OK]

Common Mistakes:

• Assuming greedy without counts works
• Confusing DP with substring problems
• Sorting breaks substring order

5. What is the time complexity of the optimal sliding window solution for counting the number of subarrays with exactly k odd numbers in an array of length n?

medium

A. O(k * n) because the window size depends on k

B. O(n^2) due to nested loops inside the sliding window

C. O(n log n) due to sorting or binary search steps

D. O(n) because each element is visited at most twice by left and right pointers

Solution

1. Step 1: Analyze pointer movements

   Right pointer moves from 0 to n-1 once; left pointer only moves forward when odd_count > k.

2. Step 2: Count total operations

   Each pointer moves at most n times, so total operations are O(n) + O(n) = O(n).

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sliding window two-pointer approach is linear time [OK]

Hint: Two pointers each move at most n times [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2)
• Confusing k factor as multiplier
• Thinking sorting is involved