Longest Repeating Character Replacement

StringSliding Window

25 min

Problem Statement

You are 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. You can perform this operation at most k times.

Return the length of the longest substring containing the same letter you can get after performing the above operations.

Example

Example 1:

Input: s = "ABAB", k = 2

Length of Longest Substring: 4

Output: 4

Explanation: Replace the two 'A's with two 'B's or vice versa.

Solution (Sliding Window)

This problem can be solved efficiently using a sliding window approach. We maintain a window and a count of the characters within it. The key is to ensure that the number of characters that need to be replaced (window size - count of most frequent character) does not exceed k.

Algorithm Steps

Initialize a hash map to store the frequency of characters in the current window, a left pointer at 0, and a result variable to 0.
Iterate through the string with a right pointer.
Increment the count of the character at the right pointer in the hash map.
While the window size minus the count of the most frequent character is greater than k, decrement the count of the character at the left pointer and move the left pointer forward.
Update the result with the maximum of the current result and the current window size.
After the loop, return the result.

Longest Repeating Character Replacement

Sliding Window Approach

Progress1 / 1

Ready to start the visualization

String `s` (k=2)

Frequency Map

Max Length

Longest Repeating Character Replacement Solution


class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        count = {}
        res = 0
        
        l = 0
        for r in range(len(s)):
            count[s[r]] = 1 + count.get(s[r], 0)
            
            while (r - l + 1) - max(count.values()) > k:
                count[s[l]] -= 1
                l += 1
                
            res = max(res, r - l + 1)
        return res