Binary search. Slower but still interesting.

• 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;
}
``````

• @lixx2100 very interesting! Thanks for the insights.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.