# 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 <= 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]