424. Longest Repeating Character Replacement — LeetCode(Python)
I got you!
Problem:
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.Constraints:
1 <= s.length <= 105sconsists of only uppercase English letters.0 <= k <= s.length
Solution:
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: #could also use if
count[s[l]] -= 1
l += 1
res = max(res, r - l + 1)
return resExplanation —
We use the sliding window technique here.
A count dictionary is maintained to keep count of the number of times a character was present in the window.
We iterate through the string and keep updating the count dictionary after encountering every character in the string.
The trick is:
A window can only have (length of window) - (frequency of maximum repeated character) number of swaps possible.
So, once this value exceeds k, we shrink the window from the left.
At every stage, the length of maximum valid window/substring is updated and stored in res.
Finally, res is returned.
Time and Space Complexity —
Iterating over the array and calling the max() function every time requires linear time because the length of count is ≤ 26.
The count dictionary needs constant extra space, since it’s length can not be more than 26, since —
sconsists of only uppercase English letters.
Thus, if n is the length of the string s,
Time Complexity: O(26*n) [real] or O(n) [amortized]
Space Complexity: O(26) [real] or O(1) [amortized]
