public class Solution {
public int[] flip(String A) {
int max = 0;
int diff = 0;
int i = 0;
int start = 0;
boolean solFound = false;
int[] ans = new int[2];
for(i = 0; i < A.length(); i++) {
char c = A.charAt(i);
diff += (c == '0') ? 1 : -1;
if(diff < 0) {
diff = 0;
start = (c == '0') ? i : i + 1;
} else {
if(max < diff) {
max = diff;
ans[0] = start;
ans[1] = i;
solFound = true;
}
}
}
if(!solFound) {
return new int[0];
}
ans[0] += 1;
ans[1] += 1;
return ans;
}
Java O(n) solution, all test passed!
bautiblacker
#1
ajay-biswas
#2
I think, I am not able to understand question statement properly.
For eg. suppose a string “1011001”. According to the solution, right answer is {5, 6}. So, if I flip 5th and 6th character (which is 0) then I will get “1011111” having six 1’s. But, if I will flip 2nd and 5th character then also I will get six 1’s (“1111101”). Wouldn’t {2, 5} be lexicographically smaller pair than {5, 6}.
Someone please help me with this.