Unlike most brilliant existing linear solutions, I solve this problem by a slower approach using binary search.

Why binary search? If we can convert a substring of length `x`

into a valid one (a string with all unique letters) using no more than `k`

replacements, then it is clear that we can also convert a substring of length no more than `x`

into a valid one. Thus, if we know how to answer the following **decision** problem efficiently, we can use binary search to guess the final answer.

**The decision problem:**

Is there a substring of length `x`

such that we can make it consist of some unique letter with no more than `k`

replacements?

The solution to this question is simple. We enumerate all substring of length `x`

. For each substring, we denote the frequency of the most frequent letters in it as `mode`

. Then, if `x - mode <= k`

, the answer is **yes**. If `x - mode > k`

holds for all substrings of length `x`

, the answer is **no**. This process can be done via a sliding-window in `O(26 * n) = O(n)`

time.

Therefore, the total runtime is `O(n log n)`

.

```
private boolean ok(char[] ch, int k, int len) {
int[] cnt = new int[26];
for (int i = 0; i < ch.length; i++) {
if (i >= len) cnt[ch[i - len] - 'A']--;
cnt[ch[i] - 'A']++;
if (i >= len - 1) {
int max = 0;
for (int j : cnt) max = Math.max(max, j);
if (len - max <= k) return true;
}
}
return false;
}
public int characterReplacement(String s, int k) {
if (s.length() == 0 || k >= s.length() - 1) return s.length();
int left = 1, right = s.length() + 1;
char[] ch = s.toCharArray();
while (left + 1 < right) {
int mid = (left + right) / 2;
if (ok(ch, k, mid)) left = mid;
else right = mid;
}
return left;
}
```