Flip

You are given a binary string(i.e. with characters 0 and 1) S consisting of characters S1, S2, …, SN. In a single operation, you can choose two indices L and R such that 1 ≤ L ≤ R ≤ N and flip the characters SL, SL+1, …, SR. By flipping, we mean change character 0 to 1 and vice-versa.

Your aim is to perform ATMOST one operation such that in final string number of 1s is maximised. If you don’t want to perform the operation, return an empty array. Else, return an array consisting of two elements denoting L and R. If there are multiple solutions, return the lexicographically smallest pair of L and R.

Notes:

For example,

S = 010

Pair of [L, R] | Final string
_______________|_____________
[1 1]          | 110
[1 2]          | 100
[1 3]          | 101
[2 2]          | 000
[2 3]          | 001

We see that two pairs [1, 1] and [1, 3] give same number of 1s in final string. So, we return [1, 1].

Another example,

If S = 111

No operation can give us more than three 1s in final string. So, we return empty array [].
思路

这题实际要找的是一个含有最多0的subarray,当含有的0一样多时,取最小的index。
我们用i, j代表当前subarray的左右index,l, r代表最多0的subarray的左右index。
cur代表当前subarray所含的0,max代表最多0的subarray所含的0。
从右往左scan array,当遇到0的时候,
  • 如果cur >= max,更新l和r。
  • 如果cur = 0,则reset j,因为这是一个新的含0的subarray

遇到1则cur--。

Solution

Time: O(n)
Space: O(1)

public class Solution {
    public ArrayList<Integer> flip(String A) {
        char[] arr = A.toCharArray();
        ArrayList<Integer> result = new ArrayList<>();
        int r = A.length() - 1;
        int l = A.length() - 1;
        int i = A.length() - 1;
        int j = A.length() - 1;
        int cur = 0;
        int max = 0;

        while (i >= 0) {
            char n = arr[i];
            if (n == '0') {
                if (cur == 0) {
                    j = i;
                } 
                if (cur + 1 >= max) {
                    r = j;
                    l = i;
                }
                cur++;
                max = Math.max(cur, max);
            } else {
                if (cur > 0) {
                    cur --;
                }
            }
            i --;
        }
        if (max == 0) return result;
        result.add(l + 1);
        result.add(r + 1);
        return result;
    }
}