package leetcode;

/**
 * https://leetcode.com/problems/flip-string-to-monotone-increasing/
 */
public class Problem926 {
    public int minFlipsMonoIncr(String S) {
        // TODO
        return 0;
    }

    public static void main(String[] args) {
        Problem926 prob = new Problem926();
        System.out.println(prob.minFlipsMonoIncr("00110")); // 1
        System.out.println(prob.minFlipsMonoIncr("010110")); // 2
        System.out.println(prob.minFlipsMonoIncr("00011000")); // 2
        System.out.println(prob.minFlipsMonoIncr("0100111")); // 1
        System.out.println(prob.minFlipsMonoIncr("100100111")); // 2
        System.out.println(prob.minFlipsMonoIncr("1001001110")); // 3
        System.out.println(prob.minFlipsMonoIncr("00001")); // 0
        System.out.println(prob.minFlipsMonoIncr("11110")); // 1
        System.out.println(prob.minFlipsMonoIncr("11100")); // 2
    }
}

package leetcode;

/**
 * https://leetcode.com/problems/flip-string-to-monotone-increasing/
 */
public class Problem926 {
    public int minFlipsMonoIncr(String S) {
        int[] sum = new int[S.length() + 1];
        for (int i = 0; i < S.length(); ++i) {
            sum[i + 1] = sum[i] + (S.charAt(i) == '1' ? 1 : 0);
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i <= S.length(); ++i) {
            // Number of ones to flip.
            int left = sum[i];
            // Number of zeros to flip.
            int right = S.length() - i - (sum[S.length()] - sum[i]);
            min = Math.min(min, left + right);
        }
        return min;
    }
}

Solve problem 926