Maximum difference of zeros and ones in binary string

The problem, simply

You get a string made only of 0 and 1. Pick one unbroken stretch of it (a substring). Count the 0s in it and the 1s in it. Give back the biggest possible value of "number of 0s minus number of 1s".

If the string has no 0 at all, the best you can do is a single 1, which scores -1. So the answer is -1.

A story to remember it

Picture it

Examples

Way 1: the simple way

Try every start and every end, and keep a running count as the end moves right.

1. For each start i, set the score to 0.
2. Move the end j from i to the last index. Add +1 for a 0, -1 for a 1.
3. After each step, compare the score with the best so far.

class Solution {
    public int maxSubstring(String s) {
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int score = 0;
            for (int j = i; j < s.length(); j++) {
                score += s.charAt(j) == '0' ? 1 : -1;   // a 0 gives a candy, a 1 takes one
                best = Math.max(best, score);
            }
        }
        return best;
    }
}

How long it takes: about n * n / 2 stretches, O(n^2). Extra room: two counters, O(1).

Way 2: the clever way

Turn each 0 into +1 and each 1 into -1. Now the question is "which stretch has the biggest total?", the famous biggest sum stretch problem.

Keep one number: the best total of a stretch that ends right here. For each new stone there are only two choices.

1. Carry on the pile from before: cur + value.
2. Start a fresh pile at this stone: value.
3. Keep the bigger one as the new cur, and update best if cur beats it.

The second row in the drawing is that "best ending here" number for every index. It is a tiny DP table that only ever looks one box back.

class Solution {
    public int maxSubstring(String s) {
        int cur = 0;
        int best = Integer.MIN_VALUE;
        for (int i = 0; i < s.length(); i++) {
            int value = s.charAt(i) == '0' ? 1 : -1;
            cur = Math.max(value, cur + value);   // carry the pile on, or start fresh
            best = Math.max(best, cur);
        }
        return best;                              // -1 when there are no zeros
    }
}

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

Watch out for

• Do not count all 0s minus all 1s of the whole string. The best stretch is often in the middle.
• A stretch must be unbroken. You cannot skip the 1s inside it.
• An empty string has no stretch at all. Ask the interviewer what to return.

What interviewers ask next

• Return the start and end of the best stretch too. Remember where the current pile started, and copy it when best improves.
• Find the longest stretch with equal 0s and 1s. Use +1 and -1 again, but now look for two equal running totals with a hash map.
• What if you may flip at most one 1 into a 0? Keep two piles: one that has not used the flip and one that has.
• Biggest total in a 2D grid of numbers? Fix a pair of columns, squash the rows, and run this same idea on the squashed column.

Remember this

Grown-up words: the candy pile is the running sum, throwing it away when it goes negative is Kadane's algorithm, the stretch is a substring, and the row of "best ending here" numbers is the DP state dp[i].