0016 - Longest Repeating Character Replacement - Revise

You are given a string s consisting of only uppercase english characters and an integer k. You can choose up to k characters of the string and replace them with any other uppercase English character.

After performing at most k replacements, return the length of the longest substring which contains only one distinct character.

Example 1:

Input: s = "XYYX", k = 2

Output: 4 Explanation: Either replace the 'X's with 'Y's, or replace the 'Y's with 'X's.

Example 2:

Input: s = "AAABABB", k = 1

Output: 5

• Window is valid if we need ≤ k replacements. Replacements needed = window_length - count_of_most_frequent_char

• When invalid, we shrink window by decrementing frequency of leftmost char and moving left pointer

• We track maximum length after every iteration, even when we shrink

• Loop through string

  • Increment count of character in each iteration
  • Post that check if window is invalid, if window length - max of values in hashmap > k
    • If it is then reduce 1 from hashmap[left pointer] and increment left pointer by 1
  • Track max window length till now

• Time: O(n) - single pass through string

• Space: O(1) - hashmap only stores 26 letters max

In [1]:

def characterReplacement(s,k):
    l=0
    res=0
    hmap = {}
    for r in range(len(s)):
        #increment number of occurences of s[r] in the window
        hmap[s[r]] = 1 + hmap.get(s[r],0)
        #window is only valid if windowLength-maxDuplicateInWindow<=k 
        if (r-l+1) - max(hmap.values())>k: #found invalid window
            #decrement number of occurences of s[l] in the window
            hmap[s[l]]-=1
            l+=1    #move to next window
        res=max(res,r-l+1)  #windowLength=r-l+1
    return res

In [2]:

characterReplacement('XYYX',2)

Out[2]:

4