Longest Repeating Character Replacement

▶

Steps

setup

Initialize frequency array and pointers

Initialize a frequency array of size 26 to zero to count characters. Set left pointer to 0, max_count to 0, and max_len to 0 before starting the iteration.

💡 This setup prepares the data structures and variables needed to track character frequencies and window boundaries efficiently.

Line:

freq = [0] * 26
left = 0
max_count = 0
max_len = 0

💡 Frequency array and pointers are ready to track the sliding window state.

expand

Expand window to include first character 'A'

Move right pointer to index 0, include 'A' in the window, and increment its frequency. Update max_count to 1 since 'A' appears once.

💡 Expanding the window adds a new character and updates frequency counts, which helps determine if the window is valid.

Line:

freq[ord(s[right]) - ord('A')] += 1
max_count = max(max_count, freq[ord(s[right]) - ord('A')])

💡 Window now contains one character 'A' with max frequency 1.

record_answer

Update max_len after first character

Calculate current window length (1) and update max_len to 1 as this is the longest valid window so far.

💡 Recording the answer tracks the longest valid substring found at each step.

Line:

max_len = max(max_len, right - left + 1)

💡 Current longest substring length is 1.

expand

Expand window to include second character 'B'

Move right pointer to index 1, include 'B' in the window, increment its frequency. max_count remains 1 as 'A' and 'B' both appear once.

💡 Adding a different character tests if the window can still be valid with replacements.

Line:

freq[ord(s[right]) - ord('A')] += 1
max_count = max(max_count, freq[ord(s[right]) - ord('A')])

💡 Window now contains 'A' and 'B' with max frequency 1.

compare

Check if window is valid and update max_len

Window size is 2, max_count is 1, replacements needed = 2 - 1 = 1 which is <= k=2, so window is valid. Update max_len to 2.

💡 This step shows how the algorithm decides if the current window can be made uniform with allowed replacements.

Line:

while (right - left + 1) - max_count > k:
    ...
max_len = max(max_len, right - left + 1)

💡 Window can be expanded because replacements needed do not exceed k.

expand

Expand window to include third character 'A'

Move right pointer to index 2, include 'A', increment frequency of 'A' to 2. Update max_count to 2 since 'A' now appears twice.

💡 Increasing max_count means fewer replacements are needed to make the window uniform.

Line:

freq[ord(s[right]) - ord('A')] += 1
max_count = max(max_count, freq[ord(s[right]) - ord('A')])

💡 Window now has 'A', 'B', 'A' with max frequency 2.

compare

Check window validity and update max_len

Window size is 3, max_count is 2, replacements needed = 3 - 2 = 1 which is <= k=2, so window is valid. Update max_len to 3.

💡 This confirms the window can still be expanded without shrinking.

Line:

while (right - left + 1) - max_count > k:
    ...
max_len = max(max_len, right - left + 1)

💡 Window size can grow while replacements remain within limit.

expand

Expand window to include fourth character 'B'

Move right pointer to index 3, include 'B', increment frequency of 'B' to 2. max_count remains 2 as 'A' and 'B' both appear twice.

💡 Adding 'B' tests if the window can still be valid with two characters having max frequency.

Line:

freq[ord(s[right]) - ord('A')] += 1
max_count = max(max_count, freq[ord(s[right]) - ord('A')])

💡 Window now contains 'A', 'B', 'A', 'B' with max frequency 2.

compare

Check window validity with full string

Window size is 4, max_count is 2, replacements needed = 4 - 2 = 2 which equals k=2, so window is valid. Update max_len to 4.

💡 This step shows the window can cover the entire string with allowed replacements.

Line:

while (right - left + 1) - max_count > k:
    ...
max_len = max(max_len, right - left + 1)

💡 Maximum window size is reached with allowed replacements.

reconstruct

Return the maximum length found

The iteration ends and the algorithm returns max_len = 4 as the length of the longest substring with at most 2 replacements.

💡 Returning the final answer completes the algorithm.

Line:

return max_len

💡 The longest valid substring length is 4 for this input.

def characterReplacement(s: str, k: int) -> int:
    freq = [0] * 26  # STEP 1
    left = 0  # STEP 1
    max_count = 0  # STEP 1
    max_len = 0  # STEP 1
    for right in range(len(s)):  # STEP 2-9
        freq[ord(s[right]) - ord('A')] += 1  # STEP 2,4,6,8
        max_count = max(max_count, freq[ord(s[right]) - ord('A')])  # STEP 2,4,6,8
        while (right - left + 1) - max_count > k:  # STEP 5,7,9
            freq[ord(s[left]) - ord('A')] -= 1  # STEP 5
            left += 1  # STEP 5
        max_len = max(max_len, right - left + 1)  # STEP 3,5,7,9
    return max_len  # STEP 10

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

📊

Longest Repeating Character Replacement - Watch the Algorithm Execute, Step by Step

Watching the algorithm step through each character and adjust the window boundaries helps you understand how the sliding window technique efficiently finds the longest substring with at most k replacements, without checking every substring explicitly.

expand

L ▼

A

0

B

1

A

2

B

3

Metric: 0

Answer: 0

expand

L=R

A

0

B

1

A

2

B

3

Window: [A]

Metric: 1

Answer: 0

record_answer

L=R

A

0

B

1

A

2

B

3

Window: [A]

Metric: 1

Answer: 1

expand

L ▼

A

0

R ▼

B

1

A

2

B

3

Window: [A, B]

Metric: 1

Answer: 1

record_answer

L ▼

A

0

R ▼

B

1

A

2

B

3

Window: [A, B]

Metric: 1

Answer: 2

expand

L ▼

A

0

B

1

R ▼

A

2

B

3

Window: [A, B, A]

Metric: 2

Answer: 2

record_answer

L ▼

A

0

B

1

R ▼

A

2

B

3

Window: [A, B, A]

Metric: 2

Answer: 3

expand

L ▼

A

0

B

1

A

2

R ▼

B

3

Window: [A, B, A, B]

Metric: 2

Answer: 3

record_answer

L ▼

A

0

B

1

A

2

R ▼

B

3

Window: [A, B, A, B]

Metric: 2

Answer: 4

record_answer

L ▼

A

0

B

1

A

2

R ▼

B

3

Window: [A, B, A, B]

Metric: 2

Answer: 4

Key Takeaways

✓ The sliding window expands greedily and only shrinks when the number of replacements needed exceeds k.

This insight is hard to see from code alone because the shrinking condition depends on the difference between window size and max frequency, which is subtle.

✓ Tracking the max frequency character in the window allows the algorithm to quickly determine if the window is valid without checking all characters.

This optimization is key to achieving linear time complexity and is easier to grasp visually.

✓ The window can cover the entire string if replacements allowed (k) are sufficient, demonstrating the algorithm's ability to find the longest possible substring.

Seeing the window expand fully with k=2 in the example clarifies how the algorithm balances window size and character frequency.

Practice

1. Consider the following Python function implementing the sliding window approach to find the maximum sum subarray of size k. What is the value of window_sum after the second iteration of the for-loop when called with arr = [1, 3, 2, 6] and k = 2?

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = window_sum
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

easy

A. 8

B. 9

C. 5

D. 7

Solution

1. Step 1: Initialize variables

   window_sum = sum(arr[:2]) = 1 + 3 = 4, max_sum = 4

2. Step 2: Iterate and update window_sum

   First iteration (i=2): window_sum = 4 + arr[2] - arr[0] = 4 + 2 - 1 = 5 Second iteration (i=3): window_sum = 5 + arr[3] - arr[1] = 5 + 6 - 3 = 8

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   window_sum after second iteration is 8 [OK]

Hint: Track window_sum updates carefully per iteration [OK]

Common Mistakes:

• Off-by-one errors in loop index
• Confusing window_sum with max_sum
• Forgetting to subtract the element leaving the window

2. Consider the following Python function that counts the number of contiguous subarrays where the product of all elements is less than k. What is the returned value when calling numSubarrayProductLessThanK([10, 5, 2, 6], 100)?

def numSubarrayProductLessThanK(nums, k):
    if k <= 1:
        return 0
    product = 1.0
    count = 0
    left = 0
    for right in range(len(nums)):
        product *= nums[right]
        while product >= k and left <= right:
            product /= nums[left]
            left += 1
        count += right - left + 1
    return count

easy

A. 8

B. 7

C. 9

D. 10

Solution

1. Step 1: Trace product and window boundaries

   Iterate right pointer: - right=0: product=10 <100, count=1 - right=1: product=50 <100, count=1+2=3 - right=2: product=100 ≥100, shrink window: product/=10=10, left=1, count=3+(2-1+1)=5 - right=3: product=10*6=60 <100, count=5+(3-1+1)=8

2. Step 2: Final count

   Total count is 8 valid subarrays.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Count matches expected output 8 [OK]

Hint: Count increments by window size each iteration [OK]

Common Mistakes:

• Off-by-one in count increment
• Not shrinking window correctly

3. The following code attempts to find the maximum sum subarray of size k using the sliding window approach. Identify the line that contains a subtle bug that may cause incorrect results when the array contains all negative numbers.

def max_sum_subarray_sliding_window(arr, k):
    n = len(arr)
    window_sum = sum(arr[:k])
    max_sum = 0
    for i in range(k, n):
        window_sum += arr[i] - arr[i - k]
        if window_sum > max_sum:
            max_sum = window_sum
    return max_sum

medium

A. Line 4: Initializing max_sum to 0 instead of a smaller value.

B. Line 5: Loop starting from index k instead of k-1.

C. Line 3: Initializing window_sum with sum of first k elements.

D. Line 6: Updating window_sum by adding arr[i] and subtracting arr[i - k].

Solution

1. Step 1: Understand initialization of max_sum

   max_sum is initialized to 0, which is incorrect if all array elements are negative because the maximum sum could be less than 0.

2. Step 2: Consequence of wrong initialization

   If all sums are negative, max_sum remains 0, which is incorrect. Proper initialization should be max_sum = window_sum (sum of first k elements) or float('-inf').

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   max_sum initialized to 0 causes incorrect max for negative arrays [OK]

Hint: Initialize max_sum to first window sum, not zero [OK]

Common Mistakes:

• Initializing max_sum to zero instead of first window sum
• Off-by-one errors in loop indices
• Incorrect window_sum updates

4. Suppose the problem is modified so that the subarray size k can vary, and you want to find the maximum sum subarray of any size between 1 and k. Which approach correctly adapts the sliding window technique to handle this variant efficiently?

hard

A. Use the original fixed-size sliding window for each size from 1 to k and take the maximum result; total time O(n*k).

B. Use a variable-size sliding window that expands and contracts dynamically to find maximum sums for all sizes up to k in O(n) time.

C. Use a prefix sum array and check all subarrays of sizes 1 to k in O(n*k) time without sliding window.

D. Use a max-heap to store sums of all subarrays of sizes 1 to k and extract the maximum in O(n log n) time.

Solution

1. Step 1: Understand the problem variant

   We want the maximum sum subarray for any size from 1 to k, not just fixed size k.

2. Step 2: Evaluate approaches

   Variable-size sliding window (B) is not straightforward here because the problem requires fixed-size subarrays for each size. Prefix sums (C) and max-heap (D) are less efficient or more complex. Running fixed-size sliding window for each size from 1 to k is simple and correct, with O(n*k) time.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sliding window repeated for each size from 1 to k -> O(n*k) [OK]

Hint: Sliding window works per fixed size; varying sizes require repeated runs [OK]

Common Mistakes:

• Assuming variable-size sliding window can handle all sizes in O(n)
• Ignoring increased complexity of varying window sizes
• Using complex data structures unnecessarily

5. Suppose the problem is modified so that characters in s1 can be reused multiple times in the substring of s2 (i.e., the substring can contain repeated characters beyond the counts in s1). Which modification to the sliding window approach correctly handles this variant?

hard

A. Remove the match count optimization and compare frequency maps at every window slide to allow repeated characters.

B. Keep the same sliding window with frequency counts and match count, but ignore counts exceeding those in s1.

C. Use a sliding window that only checks if all characters in s1 appear at least once in the window, ignoring exact counts.

D. Modify the algorithm to only check if the window contains all unique characters of s1 regardless of frequency.

Solution

1. Step 1: Understand the variant

   Allowing reuse means the substring can have more occurrences of characters than in s1. The previous match count optimization relies on exact frequency matches, which no longer applies.

2. Step 2: Identify correct approach

   To handle repeated characters beyond s1 counts, the algorithm must compare full frequency maps at each window slide, since match count optimization assumes exact matches.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Match count optimization breaks if counts can exceed s1 counts [OK]

Hint: Exact frequency match optimization fails if counts can exceed s1 [OK]

Common Mistakes:

• Assuming match count optimization still works
• Ignoring frequency counts and only checking presence