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
Solution¶
Loop through string
- Increment count of character in each iteration
- Post that check if window is invalid, if replacement needed > k. Replacements needed = window length - max of values in hashmap
- When invalid, we shrink window by decrementing frequency of leftmost char and moving left pointer
- Track max window length till now
Time: O(n) - single pass through string
Space: O(1) - hashmap only stores 26 letters max
In [3]:
def characterReplacement(s,k):
left=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-left+1) - max(hmap.values())>k: #found invalid window
#decrement number of occurences of s[left] in the window
hmap[s[left]]-=1
left+=1 #move to next window
res=max(res,r-left+1) #windowLength=r-left+1
return res
In [4]:
characterReplacement('XYYX',2)
Out[4]:
4