## Problem

**Problem ID**: 424

**Title**: Longest Repeating Character Replacement

**Difficulty**: Medium

**Description**:

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.

## Thoughts

I found this question extremely hard. Had to view the related topics before being able to derive a non-ideal O(N^2) solution and had to view the discussion to derive the optimal O(N) solution.

The main idea that I missed is that you can determine determine the number of replacement performed in O(1) time by keeping a frequency map. Number of replacement = length of curr substring - highest frequency val. Additionally any map containing characters can be traversed in O(1) time as there are only constant(26) number of keys.

## Solution

Checking a valid substring with repeating characters and less than `k`

replacement
can be done using: `substring_length - max_char_freq <= k`

.

We can solve this question by maintain a sliding window that always ensure that
`substring_length - max_char_freq <= k`

. We do so by advancing the start of the substring
whenever there is a violation.

### Implementation

```
class Solution {
public:
int characterReplacement(string s, int k) {
unordered_map<char,int> char_freq;
int n = s.length();
int start = 0;
int ans = 0;
for (int i = 0; i < n; i++) {
char_freq[s[i]]++;
int max_count = char_freq[GetMax(char_freq)];
if (i-start+1 - max_count> k) {
char_freq[s[start]]--;
start++;
}
ans = max(ans, i-start +1);
}
return ans;
}
char GetMax(const unordered_map<char,int>& m) {
int max_val = 0;
char max_c;
for (const auto [c, val] : m) {
if (val > max_val) {
max_c = c;
max_val = val;
}
}
return max_c;
}
};
```