From Brute force to slide window


  • 0
    D

    I start with the brute force methods, and improve it with sliding window.

    if substring's length - mostFreqNumCount <= k, update the result
    if substring's length - mostFreqNumCount > k, change the substring to match
    mostFreqNumCount is the count of maximum occurring character

    // Method 1: Time limit(O(26 * n^2))    
    public int characterReplacement(String s, int k) {
        if (s.length() == 0) return 0;
        int ret = 1;
        for (int i = 0 ; i < s.length() ; i++) {
            int[] hist = new int[26];
            for (int j = i ; j < s.length() ; j++) {
                hist[s.charAt(j) - 'A']++;
                int mostFreqNumCount = compuateMaxFreqCount(hist);
                int len = j - i + 1;
                if (len - mostFreqNumCount > k) {
                    break;
                }
                ret = Math.max(ret, len);
            }
        }
        return ret;
    }
    
    private int compuateMaxFreqCount(int[] hist) {
        int max = 0;
        for (int c : hist) {
            max = Math.max(c, max);
        }
        return max;
    }
    
        // Method 2 :  Similar to method 1. Don't need to keep calling compuateMaxFreqCount
    // beats 2.43% of java submissions\\
    
    public void characterReplacement(String s, int k)() {
        if (s.length() == 0) return 0;
        int ret = 1;
        int[] hist = new int[26];
        int mostFreqNumCount = 0;
        for (int i = 0 ; i < s.length() ; i++) {
            for (int j = i ; j < s.length() ; j++) {
                hist[s.charAt(j) - 'A']++;
                mostFreqNumCount = Math.max(hist[s.charAt(j) - 'A'], mostFreqNumCount);
                int len = j - i + 1;
                if (len - mostFreqNumCount > k) {
                    hist[s.charAt(i) - 'A']--;
                    i++;
                    continue;
                }
                ret = Math.max(ret, len);
            }
        }
        return ret;
    }
    
    // O(n) : Sliding window. var  i is left, var j is right
     // runtime beats 51.59% of java submissions.
    public int characterReplacement(String s, int k) {
        if (s.length() == 0) return 0;
        int ret = 1;
        int[] hist = new int[26];
        int mostFreqNumCount = 0;
        int i = 0, j = 0;
        while (j < s.length()) {
            hist[s.charAt(j) - 'A']++;
            int currMostFreqNumCount = Math.max(hist[s.charAt(j) - 'A'], mostFreqNumCount);
            int len = j - i + 1;
            while (len - currMostFreqNumCount > k) {
                hist[s.charAt(i) - 'A']--;
                currMostFreqNumCount = Math.max(hist[s.charAt(i) - 'A'], mostFreqNumCount);
                i++;
                len = j - i + 1;
            }
            mostFreqNumCount = Math.max(mostFreqNumCount, currMostFreqNumCount);
            ret = Math.max(ret, len);
            j++;
        }
        return ret;
    }

Log in to reply
 

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