> [!META]- Inline Metadata
> [tags:: #career #concepts/programming/algorithms/sliding-window ]
> [project group:: Neetcode 150]
> [difficulty:: medium]
> [status:: in progress]
> [link:: https://leetcode.com/problems/longest-repeating-character-replacement/]
> [up:: [[Leetcode MOC]]]
## 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
### Mine
#### Python
```python
from collections import Counter
class Solution:
def characterReplacement(self, s: str, k: int) -> int:
letters = Counter()
longest_substring = 0
i = 0
for j in range(len(s)):
letters[s[j]] += 1
while letters.total() - letters.most_common()[0][1] >= k + 1:
letters[s[i]] -= 1
i += 1
longest_substring = max(longest_substring, letters.total())
return longest_substring
```
#### Rust
### LC's
## Things I Learned
### Neetcode Video
$O(26n) \approx O(n)$
If we are looking at some substring, how do we know if it is valid?
Use a hashmap to keep count of each letter.
**Take len of window and count of the most frequent character, subtract them** - how many characters need to be replaced in that window.
The key is to not use an `if` condition to check that the substring is valid, but a `while`, exactly like the solution to [[3. Longest Substring Without Repeating Characters]]
## Scratchpad
We want to use a spiritually similar approach to [[3. Longest Substring Without Repeating Characters]]. We want to use a sliding window to get the longest substring **with** up to `k` other letters.