# Longest Repeating Character Replacement

- **Canonical ID**: `longest-repeating-character-replacement`
- **Canonical URL**: https://dsacheatsheet.com/problems/longest-repeating-character-replacement
- **Difficulty**: medium
- **Patterns**: Sliding Window
- **Version**: 1.0.0 (verified 2026-11-11T21:00:00Z)
- **Original Problem**: https://leetcode.com/problems/longest-repeating-character-replacement/

## 1. Core Invariant / The Trick

A window `[l..r]` is valid iff `windowLength - maxFreq <= k`. Crucial optimization: never shrink `maxFreq` down when advancing `l`, because a strictly longer window requires a strictly larger `maxFreq`!

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N)`
- **Space Complexity**: `O(1)`
- **Proof**: Eliminates inner O(26) max recalculation; `l` advances at most once per `r` step.

## 3. Minimal Idiomatic Code

### Python
```python
def characterReplacement(s: str, k: int) -> int:
    cnt = {}
    l = max_f = best = 0
    for r, c in enumerate(s):
        cnt[c] = cnt.get(c, 0) + 1
        max_f = max(max_f, cnt[c])
        while (r - l + 1) - max_f > k:
            cnt[s[l]] -= 1
            l += 1
        best = max(best, r - l + 1)
    return best
```

### TypeScript
```typescript
export function characterReplacement(s: string, k: number): number {
  const cnt = new Int32Array(26);
  let l = 0, maxF = 0, best = 0;
  for (let r = 0; r < s.length; r++) {
    const idx = s.charCodeAt(r) - 65;
    cnt[idx]++;
    if (cnt[idx] > maxF) maxF = cnt[idx];
    while (r - l + 1 - maxF > k) {
      cnt[s.charCodeAt(l) - 65]--;
      l++;
    }
    if (r - l + 1 > best) best = r - l + 1;
  }
  return best;
}
```

### C++
```cpp
int characterReplacement(string s, int k) {
    int cnt[26] = {0}, l = 0, maxF = 0, best = 0;
    for (int r = 0; r < (int)s.size(); ++r) {
        maxF = max(maxF, ++cnt[s[r] - 'A']);
        if (r - l + 1 - maxF > k) cnt[s[l++] - 'A']--;
        best = max(best, r - l + 1);
    }
    return best;
}
```

### Java
```java
int characterReplacement(String s, int k) {
    int[] cnt = new int[26]; int l = 0, maxF = 0, best = 0;
    for (int r = 0; r < s.length(); r++) {
        maxF = Math.max(maxF, ++cnt[s.charAt(r) - 'A']);
        if (r - l + 1 - maxF > k) cnt[s.charAt(l++) - 'A']--;
        best = Math.max(best, r - l + 1);
    }
    return best;
}
```

### Go
```go
func characterReplacement(s string, k int) int {
    var cnt [26]int
    l, maxF, best := 0, 0, 0
    for r := 0; r < len(s); r++ {
        cnt[s[r]-'A']++
        if cnt[s[r]-'A'] > maxF { maxF = cnt[s[r]-'A'] }
        if r-l+1-maxF > k { cnt[s[l]-'A']--; l++ }
        if r-l+1 > best { best = r - l + 1 }
    }
    return best
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Thinking `maxFreq` becomes stale breaks correctness—monotonic window size only improves when `maxFreq` strictly rises.

### Follow-ups
- Longest Subarray of 1s after flipping at most K zeros is identical with binary domain.