# Sliding Window - Longest Repeating Character Replacement

All diagrams presented herein are original creations, meticulously designed to enhance comprehension and recall. Crafting these aids required considerable effort, and I kindly request attribution if this content is reused elsewhere.

Difficulty: Easy

Map

## 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:**

1
2
3

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

**Example 2:**

1
2
3
4
5

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.
There may exists other ways to achieve this answer too.

## Solution

This is very similar problem as the Minimum Window Substring. We still need a map to keep track of letters in our window and we need to increment the `left pointer`

in a `while`

loop etc.

Start by defining three variables.

1 2 3

window_map={} l=0 max_len=0

Next, loop through the string

`s`

using right pointer`r`

and keep adding the letters to`window_map`

. Again very similar to Minimum Window Substring problem.1 2 3 4

for r in range(len(s)): # Add letter to window_map and increment # the occurrences window_map[s[r]]=1+window_map.get(s[r],0)

Now, we need the

`while`

loop to shrink to window, that is, increment the left pointer`l`

. Again, this is same as Minimum Window Substring problem. The only difference is the breaking condition.Let’s skip the

`while`

loop condition and write the logic inside. Same concept as Minimum Window Substring problem. Remove letters from the`window_map`

using`left pointer`

and keep incrementing left pointer.1 2 3

while <some logic> : window_map[s[l]] -= 1 l += 1

Now comes the main difference between the Minimum Window Substring and this problem. In the Minimum Window Substring problem, we can increment

`r`

even if`have !=need`

. So no matter if`have==need`

or`not`

we can increment`r`

.However in this problem, we wont increment

`r`

unless we are allowed to, but before that let’s decode that main logic a bit more.- set
`l, r = 0`

- Increment
`r`

till`window_len - count_of_max_repeating_char_in_that_window <= k`

- else: increment
`l`

until the above coondition is satisfied again.

- else: increment
- Keep track of
`max_len`

- set
Above is the core algorithm, however our code is now bit different. How we can align both together so that we can understand the pattern ?

- set
`l, r = 0`

- Keep incrementing
`r`

- Increment
`l`

till`window_len - count_of_max_repeating_char_in_that_window > k`

- Keep track of
`max_len`

- set
So here we just flipped the condition from

`<=k`

to`>k`

to move the left pointer`l`

. The`max_len`

calculation in this case however will be outside of the`while`

loop.1 2 3 4 5

while ((r+1)-l ) - max(window_map.values()) > k: window_map[s[l]] -= 1 l += 1 max_len = max(max_len, r-l+1)

## Visualize the Solution

## Final Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

def longest_repeating_char_replacement(self, s: str, k: int) -> int:
window_map = {}
l = 0
max_len = 0
for r in range(len(s)):
window_map[s[r]] = 1+window_map.get(s[r], 0)
while (r-l+1)-max(window_map.values()) > k:
window_map[s[l]] -= 1
l += 1
max_len = max(max_len, r-l+1)
return max_len
print(longest_repeating_char_replacement('ABAB',2))

1

```
4
```

## Runtime Complexity

The runtime will be `O(n)`

as we are simply scanning through the array once.