Split the Binary string into two substring with equal 0s and 1s

The problem, simply

You get a string made only of 0 and 1. Cut it into pieces that sit next to each other and use every character. Each piece must have the same number of 0s and 1s.

Give back the largest number of pieces you can make. If there is no way at all, give back -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Make the shortest fair piece you can, then start the next piece right after it. To check whether a piece is fair, count its 0s and 1s from scratch.

1. Start a piece at start.
2. Try end = start, start + 1, .... For each one, count the 0s and 1s in s[start..end].
3. The first end where the counts are equal closes the piece. Add one to the answer and set start = end + 1.
4. If no end works, the rest of the string can never be fair, so return -1.

Why the shortest piece? Cutting early never hurts. If a piece is fair, what comes after it still needs to be fair on its own, and cutting earlier gives you more pieces.

class Solution {
    public int maxSplits(String s) {
        int n = s.length(), pieces = 0, start = 0;
        while (start < n) {
            int end = -1;
            for (int e = start; e < n && end == -1; e++) {
                int zeros = 0, ones = 0;
                for (int k = start; k <= e; k++) {      // count from scratch
                    if (s.charAt(k) == '0') zeros++; else ones++;
                }
                if (zeros == ones) end = e;             // shortest fair piece
            }
            if (end == -1) return -1;                   // the rest can never be fair
            pieces++;
            start = end + 1;
        }
        return pieces;
    }
}

How long it takes: for a piece of length m we recount up to m times, so up to m * m steps. All pieces together cost at most O(n^2). Extra room: two counters, O(1).

Way 2: the clever way

Do not recount. Keep the seesaw score as you walk: plus one for a 0, minus one for a 1. The score at any point is (0s so far) minus (1s so far).

1. Walk the string once, updating balance.
2. Every time balance becomes 0, the part since the last cut is fair. Count a piece.
3. At the end, if balance is not 0, the last part is unfair, so return -1.

A cut is only possible where the score is zero, and cutting at every zero gives fair pieces. So the number of zeros is the answer.

class Solution {
    public int maxSplits(String s) {
        int balance = 0, pieces = 0;
        for (int i = 0; i < s.length(); i++) {
            balance += (s.charAt(i) == '0') ? 1 : -1;  // red kid +1, blue kid -1
            if (balance == 0) pieces++;               // level: a fair piece ends here
        }
        return balance == 0 ? pieces : -1;            // the last part must be fair too
    }
}

How long it takes: one walk, O(n). Extra room: two numbers, O(1).

Watch out for

• An empty string. There are no pieces, so return 0, or whatever the interviewer defines. Ask.
• Only comparing the totals. Equal totals tell you the answer is at least 1, not how many pieces you can make.
• Returning the list of pieces instead of the count. Remember the index of the last cut and use s.substring(start, i + 1) at each zero.

What interviewers ask next

• Print the pieces too. Keep start, and at every zero add s.substring(start, i + 1) and set start = i + 1.
• What if the balance can go below zero? That is fine here. It only matters in bracket problems, where a ) before its ( is not allowed.
• Longest part with equal 0s and 1s, not starting at the front (LeetCode 525). Store the first index of each balance in a map. When a balance repeats, the part between is level.
• Count all fair parts, not only the cuts (LeetCode 696 and similar). Same balance idea, but count how many earlier positions had the same balance.
• Is cutting at every zero always the maximum? Yes. Any valid cut must be at a zero, so you cannot have more cuts than zeros.

Remember this

Grown-up words: the seesaw score is a running balance (a prefix sum of plus and minus ones), cutting at the earliest level point is a greedy choice, and the level points are where the prefix sum equals zero.