Longest repeating character replacement#

Levels: level-4

Data structures: string

Patterns: sliding-window

Practice Link#

LeetCode

Description#

Given a string s that consists of only uppercase english letters, you can perform at most k operations on that string.
In one operation, you can choose any character of the string and change it to any other uppercase English character.
Find the length of the longest sub-string containing all repeating letters you can get after performing the above operations.

Note:

Both the string’s length and k will not exceed 10^4.

Examples#

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

1Input: s = "AABABBA", k = 1
2
3Output: 4
4
5Explanation:
6Replace the one 'A' in the middle with 'B' and form "AABBBBA".
7The substring "BBBB" has the longest repeating letters, which is 4.

Thinking#

Can this have a sliding window based implementation?

Python Solution#

 1import collections
 2
 3
 4class Solution:
 5    def characterReplacement(self, s, k):
 6        counts = collections.Counter()
 7        start = res = 0
 8        
 9        # We use a window ranging from index start to end
10        # We only look in characters inside this window and keep track of their counts
11        # We can allow up to K chars that are not the most frequent char in our window
12        
13        for end in range(len(s)):
14            # at each loop, end is shifted to the right
15            counts[s[end]] += 1 # we've seen character 's[end]' one more time in the this new window
16            
17            # we shift start to the right only if we ran out of replacements
18            # we ran out of replacements if (CHARS that are not the most frequent in current window) > k
19            # (end - start + 1) is length of our window, because our window range is INCLUSIVE of both ends
20            if end - start + 1 - counts.most_common(1)[0][1] > k:
21                # since our window will be shifted, we subtract the character that we are shifting away from by 1
22                # because it will no longer be in the new window
23                counts[s[start]] -= 1 
24                start += 1 # now shift our window
25            
26            # at each window, simply update res if our current window is larger
27            res = max(res, end - start + 1)
28        
29        return res