Skip to content

424. Longest Repeating Character Replacement

Hard

Description

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 1:

Input: s = "ABAB", k = 2
Output: 4
Explanation: Replace the two 'A's with two 'B's or vice versa.

Example 2:

Input: s = "AABABBA", k = 1
Output: 4
Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA".
The substring "BBBB" has the longest repeating letters, which is 4.
There may exists other ways to achieve this answer too.

Constraints:

  • 1 <= s.length <= 10⁡
  • s consists of only uppercase English letters.
  • 0 <= k <= s.length

Solutions πŸ”’

Algorithm Discussion

Sliding Window

  1. We can keep tracking a current window, and use two pointer to apply the sliding window algorithms.

  2. We can expand the window to the right greedily as long as the character is not existent in the current window.

  3. Otherwise, we need to move the left pointer and erase the corresponding characters at left pointer out of the window until the current character at the right pointer is no longer in the window.

  4. If we don’t move the left pointer (shrink the window), the window is not valid no matter how we move the right pointer.

The time complexity is \(O(n)\) as the left and right pointers both move towards the right and the space complexity is \(O(n)\) as we need a hash-set or dictionary to store the elements in the current window.

Procedure Sliding_Window_Flexible_Longest

def slidingWindowFlexibleLongest(input):

    initialize window, ans
    left = 0

    for right in range(len(input)):
        append input[right] to window

        while invalid(window):        # update left until window is valid again
            remove input[left] from window
            left += 1

        ans = max(ans, window)        # window is guaranteed to be valid here
    return ans

Approach: HashTable + SlidingWindow

Time complexity: \(O(n)\)

Space complexity: \(O(1)\)

Algorithm

The problem can be efficiently solved using the sliding window technique.

We maintain a window that contains the maximum number of repeating characters possible with at most k replacements.

Counter() count is used to keep track of the frequency of characters within the current window.

maxCount keeps track of the highest frequency of any single character within the current window, which helps us determine how many replacements we can afford.

If the current window size minus maxCount exceeds k, it indicates that we need more than k replacements to make all characters in the window the same, thus we shrink the window from the left.

We continuously update the answer with the maximum valid window size encountered during the process.

The time complexity is \(O(n)\), where n is the length of the string s. This is because each character in the string is processed at most twice, once when expanding the window and once when shrinking it.

The space complexity \(O(1)\), despite using a Counter, the space complexity is constant because the input string consists of only uppercase English letters, limiting the number of unique keys in the Counter to 26.

from collections import Counter
class Solution:
    def characterReplacement(self, s: str, k: int) -> int:
        ans = 0
        count = Counter()                   #window, a hashtable to store the frequencies of characters like this {A:1,B:1,....}
        maxCount = 0                        # to store the frequncy of maximum character count
        l = 0

        for r in range(len(s)):
            count[s[r]]+=1                  #expand the window i.e add the count of incoming character in window
            maxCount = max(maxCount,count[s[r]])

            while (r-l+1) - maxCount > k:   #window condition broken or invalid window condition , when length of window (r-l+1) minus maxCharacterCount becomes more than the k (the character can be replaced) meaning we can only expand the window until we consume the provided characters count
                count[s[l]]-=1              #shrink the window
                l+=1                        #slide the window

            ans = max(ans,r-l+1)

        return ans
Akhil Singh Chauhan Akhil Singh Chauhan
Creator

Comments