We have N
times to flip 0 to 1 in array. Find the longest continuous 1 after we
flipped the N zero elements. Rotation is allowed.
For example, 100100111000, n=2, the best flip is 100111111000, return 6
10001101101, n=2, the best flip is 10001111111, return 8(rotation is allowed)
The following algorithm is more like a inch worm walking on a line, it tries to go forward as it can, then shrink from the tail, then move forward again.
/**
* we first concatenate string to itself
*
* then use a sliding window, keep track of number of 0s in the window
* grow the right side of window if not exceed max 0s allowed
* otherwise shrink the left side to reduce the 0s
*
* the algorithm stops when left side reach the length of original string
*
*/
public static int maxContinuous1sWithRotation(String s, int maxFlips){
int p1=0, p2=0, len = s.length(), num0=0, max=0;
while(p1<len && p2-p1<len){
if(s.charAt(p2%len) == '0'){
num0++;
}
/*
* if num0 reaches maxFlips+1
* we need to shrink the sliding window from left
* until we reaches a 0 and reduce the counter
*/
if(num0 > maxFlips){
while(p1<len && s.charAt(p1)=='1')
p1++;
p1++; num0--;
}
/*
* we keep on growing the sliding window
* to the right and update the max
*/
p2++;
max = Math.max(max, p2-p1);
}
return max;
}
* we first concatenate string to itself
*
* then use a sliding window, keep track of number of 0s in the window
* grow the right side of window if not exceed max 0s allowed
* otherwise shrink the left side to reduce the 0s
*
* the algorithm stops when left side reach the length of original string
*
*/
public static int maxContinuous1sWithRotation(String s, int maxFlips){
int p1=0, p2=0, len = s.length(), num0=0, max=0;
while(p1<len && p2-p1<len){
if(s.charAt(p2%len) == '0'){
num0++;
}
/*
* if num0 reaches maxFlips+1
* we need to shrink the sliding window from left
* until we reaches a 0 and reduce the counter
*/
if(num0 > maxFlips){
while(p1<len && s.charAt(p1)=='1')
p1++;
p1++; num0--;
}
/*
* we keep on growing the sliding window
* to the right and update the max
*/
p2++;
max = Math.max(max, p2-p1);
}
return max;
}
Try ("1111", 1), ("11011", 1), ("11011", 2)
ReplyDelete