424. Longest Repeating Character Replacement — LeetCode(Python)

Palash Sharma
2 min readJul 8, 2022

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 <= 105
  • s consists 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 res

Explanation —

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 —

s consists 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]

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏

--

--