From Brute force to slide window

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

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