Binary search. Slower but still interesting.


  • 3
    L

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

  • 0
    T

    @lixx2100 very interesting! Thanks for the insights.


Log in to reply
 

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