Java simple O(n) solution


#1

public class Solution {
public ArrayList flip(String A) {
int curStart = 0;
int curEnd = 0;
int start = 0;
int end = 0;
int max = 0;
int curMax = 0;
boolean flag = false;
for (int i=0; i<A.length(); i++) {
if (A.charAt(i) == ‘0’) {
flag = true;
curMax++;
curEnd = i;
} else curMax–;

        if (curMax > max) {
            start = curStart;
            end = curEnd;
            max = curMax;
        } else if (curMax < 0) {
            curMax = 0;
            curStart = i+1;
            curEnd = i+1;
        }
    }
    ArrayList<Integer> vals = new ArrayList<>();
    if (!flag) return vals;
    vals.add(start+1);
    vals.add(end+1);
    return vals;
}

}