https://leetcode.com/problems/longest-repeating-character-replacement/
https://discuss.leetcode.com/topic/63471/java-sliding-window-easy-to-understand
The true meaning of his
So it is all right that
https://discuss.leetcode.com/topic/63416/sliding-window-similar-to-finding-longest-substring-with-k-distinct-characters/5
X. Sliding window
https://leetcode.com/problems/longest-repeating-character-replacement/discuss/91271/Java-12-lines-O(n)-sliding-window-solution-with-explanation
http://blog.csdn.net/MebiuW/article/details/52830364
X. DFS http://brookebian.blogspot.com/2016/10/424-longest-repeating-character.html
http://bookshadow.com/weblog/2016/10/16/leetcode-longest-repeating-character-replacement/
http://www.cnblogs.com/EdwardLiu/p/6359777.html
Given a string that consists of only uppercase English letters, you can replace any letter in the string with another letter at most k times. Find the length of a longest substring containing all repeating letters you can get after performing the above operations.
Note:
Both the string's length and k will not exceed 104.
Both the string's length and k will not exceed 104.
Example 1:
Input: s = "ABAB", k = 2 Output: 4 Explanation: Replace the two 'A's with two 'B's or vice versa.
Example 2:
Input: s = "AABABBA", k = 1 Output: 4 Explanation: Replace the one 'A' in the middle with 'B' and form "AABBBBA". The substring "BBBB" has the longest repeating letters, which is 4.
https://discuss.leetcode.com/topic/63471/java-sliding-window-easy-to-understand
The problem is similar to longest substring with most K distinct characte. But this time, the constraint is we can only have most K characters that is different with the most frequent character in the substring. For example in the sliding window:
"ABBBAC" most frequent character is B with count 3, all other character is count as different to B,
which is A and C, and the result is 2 + 1 = 3.
Each time we count the different characters. If it is not bigger than k we extend the sliding window.
Since we only have 26 characters, keep the count in a integer array is good enough.
Since we only have 26 characters, keep the count in a integer array is good enough.
public int characterReplacement(String s, int k) {
if(s == null || s.length() == 0){
return 0;
}
int max = 0;
int[] ch = new int[26];
char[] str = s.toCharArray();
for(int i=0, j=0; i<s.length(); i++){
while(j < s.length()){
ch[str[j] - 'A']++;
if(count(ch) > k){ //If exceed k, break
ch[str[j] - 'A']--;
break;
}
j++;
}
max = Math.max(max, j-i);
ch[str[i] - 'A']--;
}
return max;
}
//Count the number of character that is different to the longest character
public int count(int[] ch){
int max = 0;
int sum = 0;
for(int val:ch){
sum += val;
max = Math.max(max, val);
}
return sum - max;
}The true meaning of his
max_same is the window_size. (i.e. windows_size = max_same + k).So it is all right that
window_size never decreases since we are only interested in finding the biggest window.https://discuss.leetcode.com/topic/63416/sliding-window-similar-to-finding-longest-substring-with-k-distinct-characters/5
The problem says that we can make at most k changes to the string (any character can be replaced with any other character). So, let's say there were no constraints like the k. Given a string convert it to a string with all same characters with minimal changes. The answer to this is
length of the entire string - number of times of the maximum occurring character in the string
Given this, we can apply the at most k changes constraint and maintain a sliding window such that
(length of substring - number of times of the maximum occurring character in the substring) <= k
int characterReplacement(string s, int k) {
vector<int> counts(26, 0);
int start = 0;
int maxCharCount = 0;
int n = s.length();
int result = 0;
for(int end = 0; end < n; end++){
counts[s[end]-'A']++;
if(maxCharCount < counts[s[end]-'A']){
maxCharCount = counts[s[end]-'A'];
}
while(end-start-maxCharCount+1 > k){
counts[s[start]-'A']--;
start++;
for(int i = 0; i < 26; i++){
if(maxCharCount < counts[i]){
maxCharCount = counts[i];
}
}
}
result = max(result, end-start+1);
}
return result;
}X. Sliding window
https://leetcode.com/problems/longest-repeating-character-replacement/discuss/91271/Java-12-lines-O(n)-sliding-window-solution-with-explanation
public int characterReplacement(String s, int k) {
int len = s.length();
int[] count = new int[26];
int start = 0, maxCount = 0, maxLength = 0;
for (int end = 0; end < len; end++) {
maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
while (end - start + 1 - maxCount > k) {
count[s.charAt(start) - 'A']--;
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}
There's no edge case for this question. The initial step is to extend the window to its limit, that is, the longest we can get to with maximum number of modifications. Until then the variable start will remain at 0.
Then as end increase, the whole substring from 0 to end will violate the rule, so we need to update start accordingly (slide the window). We move start to the right until the whole string satisfy the constraint again. Then each time we reach such situation, we update our max length.
http://bookshadow.com/weblog/2016/10/16/leetcode-longest-repeating-character-replacement/
定义一段区间内出现次数最多的字符为“优势字符”
维护有效区间[p1, p2]，使得区间内除“优势字符”外的其余字符个数不大于k
时间复杂度O(m * n)，其中m为字母个数, n为字符串长度
public int characterReplacement(String s, int k) {
int[] cArr = new int[26];
int maxCount = 0, start = 0, maxSize = 0;
for(int end = 0; end < s.length(); end ++){
cArr[s.charAt(end) - 'A']++;
maxCount = Math.max(maxCount, cArr[s.charAt(end) - 'A']);
// if max character frequency + distance between start and end is greater than k
// this means we have considered changing more than k charactres. So time to shrink window
if(end - start + 1 - maxCount > k){
cArr[s.charAt(start) - 'A']--;
start ++;
}
maxSize = Math.max(maxSize, end - start + 1);
}
return maxSize;
}
Since we are only interested in the longest valid substring, our sliding windows need not shrink, even if a window may cover an invalid substring. We either grow the window by appending one char on the right, or shift the whole window to the right by one. And we only grow the window when the count of the new char exceeds the historical max count (from a previous window that covers a valid substring).
That is, we do not need the accurate max count of the current window; we only care if the max count exceeds the historical max count; and that can only happen because of the new char.
https://discuss.leetcode.com/topic/63494/java-12-lines-o-n-sliding-window-solution-with-explanation public int characterReplacement(String s, int k) {
int len = s.length();
int[] count = new int[26];
int start = 0, maxCount = 0, maxLength = 0;
for (int end = 0; end < len; end++) {
maxCount = Math.max(maxCount, ++count[s.charAt(end) - 'A']);
while (end - start + 1 - maxCount > k) {
count[s.charAt(start) - 'A']--;
start++;
}
maxLength = Math.max(maxLength, end - start + 1);
}
return maxLength;
}http://blog.csdn.net/MebiuW/article/details/52830364
The idea is to find maximum valid substring with repeated character 'A' to 'Z' respectively. For each case, use sliding window to determine its maximum length, update the global maximum length if needed.
public int characterReplacement(String s, int k) {
int maxLen = 0;
for(int l = 0 ; l<26;l++){
char c = (char)('A' + l); //repeated char we are looking for
int i = 0, j = 0, count = 0;
while(j<s.length()){
char cur = s.charAt(j);
if(cur != c) count++;
//make the substring valid again
while(count > k){
if(s.charAt(i) != c) count--;
i++;
}
//update maximun len
maxLen = Math.max(maxLen,j-i+1);
j++;
}
}
return maxLen;
} Set<Character> dict = new HashSet<>();
int max = 0;
public int characterReplacement(String s, int k) {
if(s.length() == 0) return 0;
for(int i = 0; i < s.length(); i++)
dict.add(s.charAt(i));
dfs(s.toCharArray(),k,new HashSet<>());
return max;
}
public void dfs(char[] chars,int k,Set<Integer> visited){
int[] count = count(String.valueOf(chars));
max = Math.max(count[count.length-1],max);
if(k == 0)
return;
for(int i = 0; i < chars.length; i++){
if(visited.contains(i))
continue;
char tmp = chars[i];
for(char c: dict){
if(c==tmp )
continue;
chars[i] = c;
visited.add(i);
dfs(chars,k-1,visited);
visited.remove(i);
}
chars[i] = tmp;
}
return ;
}
public int[] count(String s){
int[] count = new int[s.length()+1];
count[0]=1;
count[s.length()-1]=1;
int max = 1;
for(int i = 1; i < s.length(); i++){
count[i] = s.charAt(i) != s.charAt(i-1)? 1:count[i-1] + 1;
max = Math.max(max,count[i]);
}
for(int i = s.length()-2; i >= 0; i--){
if(s.charAt(i) == s.charAt(i+1))
count[i] = count[i+1];
}
count[s.length()]=max;
return count;
}
public int[] copy(int[] nums){
int n = nums.length;
int[] copy = new int[n];
for(int i = 0; i < n; i++){
copy[i] = nums[i];
}
return copy;
} http://bookshadow.com/weblog/2016/10/16/leetcode-longest-repeating-character-replacement/
解法II 统计单词连续区间 + 枚举字母 + 枚举区间起止点
时间复杂度O(m * n)，其中m为字母个数, n为区间数
首先统计出字符串内各单词所在的连续区间，记为cdict，例如AABABBA得到的区间为{A : [(0, 1), (3, 3), (6, 6)], B : [(2, 2), (4, 5)]}
然后枚举需要保留的字母
尝试用k值填补区间之间的间隙，并更新最优答案。
def characterReplacement(self, s, k):
"""
:type s: str
:type k: int
:rtype: int
"""
sizes = len(s)
letters = set(s)
cdict = collections.defaultdict(list)
li, lc = 0, (s[0] if s else None)
for i, c in enumerate(s):
if c != lc:
cdict[lc].append( (li, i - 1) )
li, lc = i, c
cdict[lc].append( (li, sizes - 1) )
ans = 0
for c in letters:
invs = cdict[c]
ans = max(ans, max(y - x + 1 + min(k, x + sizes - 1 - y) for x, y in invs))
sizec = len(invs)
cnt = k
sp = 0
ep = 1
while sp < sizec and ep < sizec:
if cnt >= invs[ep][0] - invs[ep - 1][1] - 1:
cnt -= invs[ep][0] - invs[ep - 1][1] - 1
lenc = invs[ep][1] - invs[sp][0] + 1 + min(cnt, invs[sp][0] + sizes - 1 - invs[ep][1])
ans = max(ans, lenc)
ep += 1
else:
sp += 1
cnt += invs[sp][0] - invs[sp - 1][1] - 1
return anshttp://www.cnblogs.com/EdwardLiu/p/6359777.html
give a string, all 1 or 0, we can flip a 0 to 1, find the longest 1 substring after the flipping
这是一个简单版本of LC 424 Longest Repeating Character Replacement
又是Window, 又是Two Pointers
Window还是采用每次都try to update left使得window valid, 每次都检查最大window
5 public static int find2(String str) { 6 if (str==null || str.length()==0) return 0; 7 int l = 0, r = 0; 8 int maxLen = 0; 9 int countZero = 0; 10 for (r=0; r<str.length(); r++) { 11 if (str.charAt(r) == '0') countZero++; 12 while (countZero > 1 && l < str.length()) { 13 if (str.charAt(l) == '0') countZero--; 14 l++; 15 } 16 maxLen = Math.max(r-l+1, maxLen); 17 } 18 return maxLen; 19 }
