LeetCode 424 - Longest Repeating Character Replacement

The problem gives us a string s consisting only of uppercase English letters and an integer k. We are allowed to perform at most k replacement operations. In one operation, we can change any character in the string into any other uppercase English character.

leetcodemediumhash-tablestringsliding-window

LeetCode Problem 424

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sliding Window

Solution

Problem Understanding

The problem gives us a string s consisting only of uppercase English letters and an integer k. We are allowed to perform at most k replacement operations. In one operation, we can change any character in the string into any other uppercase English character.

The goal is to find the length of the longest substring that can be transformed into a substring containing only one repeated character after performing at most k replacements.

In simpler terms, we want the largest contiguous section of the string where we can make all characters identical by changing at most k characters.

For example, consider the substring "AABA" with k = 1. This substring can become "AAAA" by replacing the single 'B' with 'A'. Since only one replacement is needed, the substring is valid.

The input constraints are important:

  • The string length can be as large as 10^5
  • The string contains only uppercase English letters
  • k can range from 0 to the length of the string

These constraints immediately tell us that an O(n^2) or worse solution may become too slow for large inputs. We need an algorithm that processes the string efficiently, ideally in linear time.

Several edge cases are important:

  • When k = 0, we cannot replace anything, so we are simply looking for the longest sequence of identical consecutive characters.
  • When k >= len(s), the entire string can always be transformed into a single repeated character.
  • Strings with all identical characters should return the full string length immediately.
  • Strings with highly alternating characters, such as "ABABABAB", stress whether the algorithm correctly maintains replacement counts.

Approaches

Brute Force Approach

A straightforward solution is to examine every possible substring and determine whether it can be converted into a substring of identical characters using at most k replacements.

For each substring:

  1. Count the frequency of every character.
  2. Identify the character with the highest frequency.
  3. Compute how many replacements are needed.

If a substring has length L and the most frequent character appears maxFreq times, then:

replacementsNeeded = L - maxFreq

This works because the optimal strategy is always to keep the most common character and replace all others.

If replacementsNeeded <= k, then the substring is valid.

The brute force method is correct because it exhaustively checks every possible substring. However, it is too slow for the input constraints. There are O(n^2) substrings, and evaluating each substring may take O(26) or more time.

Key Insight for the Optimal Solution

The critical observation is that for a substring to be valid:

windowLength - maxCharacterFrequency <= k

This means the number of characters that are not the dominant character must not exceed k.

Instead of checking every substring independently, we can use a sliding window. The idea is to maintain the largest valid window while expanding the right boundary one character at a time.

As we expand the window:

  • We track character frequencies.
  • We track the frequency of the most common character in the current window.
  • If the window becomes invalid, we shrink it from the left until it becomes valid again.

This allows us to process each character at most twice, once when entering the window and once when leaving it, giving an O(n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(n²) O(1) Checks every substring independently
Optimal O(n) O(1) Sliding window with frequency tracking

Algorithm Walkthrough

Optimal Sliding Window Algorithm

  1. Initialize two pointers, left and right, representing the current window boundaries.

The window will represent the substring currently being analyzed. 2. Maintain a frequency map for characters inside the current window.

Since the string contains only uppercase English letters, the map size is bounded by 26. 3. Track the frequency of the most common character in the current window.

This value is crucial because the number of required replacements is:

windowSize - maxFrequency
  1. Expand the window by moving right one step at a time.

For each new character:

  • Increase its frequency in the map.
  • Update maxFrequency if needed.
  1. Check whether the current window is valid.

The window is valid if:

(right - left + 1) - maxFrequency <= k

This means we can replace all non-dominant characters within the allowed number of operations. 6. If the window becomes invalid, shrink it from the left.

  • Decrease the frequency of s[left]
  • Move left forward

Continue shrinking until the window becomes valid again. 7. Track the maximum valid window length seen so far.

Since every valid window represents a candidate answer, we continuously update the best result.

Why it works

The sliding window maintains the invariant that the current window is always either valid or adjusted immediately when it becomes invalid. The key observation is that the minimum number of replacements needed for a window depends only on the most frequent character in that window.

By always expanding greedily and shrinking only when necessary, we ensure that every valid window is considered efficiently. Since each pointer moves at most n times, the algorithm runs in linear time.

Python Solution

class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        frequency = {}
        
        left = 0
        max_frequency = 0
        longest = 0
        
        for right in range(len(s)):
            current_char = s[right]
            
            frequency[current_char] = frequency.get(current_char, 0) + 1
            
            max_frequency = max(
                max_frequency,
                frequency[current_char]
            )
            
            window_length = right - left + 1
            
            while window_length - max_frequency > k:
                left_char = s[left]
                frequency[left_char] -= 1
                left += 1
                
                window_length = right - left + 1
            
            longest = max(longest, window_length)
        
        return longest

The implementation begins by creating a frequency dictionary to store the count of each character inside the current window.

The left pointer marks the beginning of the sliding window, while the right pointer expands through the string.

Whenever a new character enters the window, its frequency is incremented. We also update max_frequency, which stores the highest frequency of any character seen within the current window.

The central validity condition is:

window_length - max_frequency <= k

If this condition fails, the window requires too many replacements, so we shrink it from the left until it becomes valid again.

At every step, we update longest with the largest valid window length encountered.

An important optimization is that max_frequency is never decreased. Even though it may occasionally become stale, the algorithm still works correctly because the window only shrinks when definitely invalid. This preserves linear complexity.

Go Solution

func characterReplacement(s string, k int) int {
    frequency := make(map[byte]int)

    left := 0
    maxFrequency := 0
    longest := 0

    for right := 0; right < len(s); right++ {
        currentChar := s[right]

        frequency[currentChar]++

        if frequency[currentChar] > maxFrequency {
            maxFrequency = frequency[currentChar]
        }

        windowLength := right - left + 1

        for windowLength-maxFrequency > k {
            leftChar := s[left]
            frequency[leftChar]--

            left++
            windowLength = right - left + 1
        }

        if windowLength > longest {
            longest = windowLength
        }
    }

    return longest
}

The Go implementation follows the same sliding window logic as the Python version.

A map[byte]int is used for character frequencies because the string contains ASCII uppercase letters. Go strings are byte-indexable, so using byte is efficient.

Unlike Python dictionaries, Go maps require explicit existence handling, but incrementing nonexistent keys works naturally because missing entries default to zero.

Integer overflow is not a concern because the maximum string length is only 10^5.

Worked Examples

Example 1

Input:

s = "ABAB"
k = 2

We trace the sliding window step by step.

Step Right Char Window Frequencies maxFrequency Window Length Replacements Needed Valid
1 A A A:1 1 1 0 Yes
2 B AB A:1 B:1 1 2 1 Yes
3 A ABA A:2 B:1 2 3 1 Yes
4 B ABAB A:2 B:2 2 4 2 Yes

The entire string is valid because changing two characters is allowed.

Final answer:

4

Example 2

Input:

s = "AABABBA"
k = 1
Step Right Char Window Frequencies maxFrequency Window Length Replacements Needed Action
1 A A A:1 1 1 0 Keep
2 A AA A:2 2 2 0 Keep
3 B AAB A:2 B:1 2 3 1 Keep
4 A AABA A:3 B:1 3 4 1 Keep
5 B AABAB A:3 B:2 3 5 2 Shrink
6 Remove left A ABAB A:2 B:2 3 4 1 Valid
7 B ABABB A:2 B:3 3 5 2 Shrink
8 Remove left A BABB A:1 B:3 3 4 1 Valid
9 A BABBA A:2 B:3 3 5 2 Shrink

The maximum valid window length encountered is 4.

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each pointer moves through the string at most once
Space O(1) At most 26 uppercase character counts are stored

The time complexity is linear because the sliding window expands and contracts efficiently. Although there is a nested while loop, each character is added and removed from the window at most one time.

The space complexity is constant because the frequency map contains at most 26 entries, regardless of input size.

Test Cases

solution = Solution()

assert solution.characterReplacement("ABAB", 2) == 4
# Entire string can become identical

assert solution.characterReplacement("AABABBA", 1) == 4
# Standard example from problem statement

assert solution.characterReplacement("AAAA", 2) == 4
# Already uniform string

assert solution.characterReplacement("ABCDE", 1) == 2
# Only one replacement allowed

assert solution.characterReplacement("A", 0) == 1
# Single character edge case

assert solution.characterReplacement("ABBB", 2) == 4
# Convert A into B

assert solution.characterReplacement("BAAA", 0) == 3
# No replacements allowed

assert solution.characterReplacement("ABAA", 0) == 2
# Longest existing repeated substring

assert solution.characterReplacement("ABABBA", 2) == 5
# Sliding window must shrink correctly

assert solution.characterReplacement("ABCDEFG", 7) == 7
# k equals string length

assert solution.characterReplacement("ABCD", 4) == 4
# Entire string replaceable

assert solution.characterReplacement("AABCCBB", 2) == 5
# Multiple possible valid windows

assert solution.characterReplacement("ABABABAB", 1) == 3
# Alternating pattern stress case
Test Why
"ABAB", 2 Verifies standard replacement behavior
"AABABBA", 1 Tests shrinking logic
"AAAA", 2 Already uniform input
"ABCDE", 1 Distinct characters
"A", 0 Minimum input size
"ABBB", 2 Full conversion possible
"BAAA", 0 No replacements allowed
"ABAA", 0 Finds longest natural run
"ABABBA", 2 Validates dynamic window adjustment
"ABCDEFG", 7 All characters replaceable
"ABCD", 4 Replacement budget equals length
"AABCCBB", 2 Competing character frequencies
"ABABABAB", 1 Alternating character stress test

Edge Cases

Case 1: No Replacements Allowed

Consider:

s = "ABAA"
k = 0

A buggy implementation might still attempt to expand windows containing mixed characters. However, when k = 0, only substrings already consisting of identical characters are valid.

The algorithm handles this naturally because the validity condition becomes:

windowLength - maxFrequency <= 0

This is only true when every character in the window is identical.

Case 2: Entire String Can Be Replaced

Consider:

s = "ABCDE"
k = 5

Since we may replace every character if needed, the answer should be the entire string length.

Some implementations incorrectly shrink the window unnecessarily. The sliding window solution correctly recognizes that:

5 - 1 <= 5

so the whole string remains valid.

Case 3: Alternating Characters

Consider:

s = "ABABABAB"
k = 1

Alternating patterns are tricky because the window repeatedly becomes invalid as it grows.

A naive implementation may incorrectly track the dominant frequency after shrinking. This solution avoids that issue by maintaining a non-decreasing max_frequency, which still guarantees correctness while preserving linear runtime.

Case 4: Single Character String

Consider:

s = "A"
k = 0

Small inputs often expose off-by-one errors in window calculations.

The implementation correctly initializes the window, processes the single character, and returns 1 without requiring any special-case handling.