Maximum difference of zeros and ones in binary string

Problem Statement

Given a binary string (containing only '0' and '1'), find the maximum difference between the number of 0s and 1s in any substring. In other words, find a substring that maximizes (count of 0s - count of 1s).

Example:

• Input: s = "11000010001"
• Output: 6 (Substring "0000100" has 6 zeros and 1 one → difference = 5; but "000001000" gives difference 6)

Noob-Friendly Explanation

Imagine you have a string of coins — some are fake (0) and some are real (1). You want to find a consecutive section of the string where you have the most fake coins compared to real ones. Every fake coin adds +1 to your score and every real coin adds -1. Find the section with the highest score.

Approach 1: Brute Force

Intuition

Check every possible substring. For each substring, count the number of 0s and 1s, calculate the difference, and track the maximum.

Algorithm

1. For each starting index i, iterate through all ending indices j.
2. Count 0s and 1s in the substring from i to j.
3. Compute count0 - count1 and track the maximum.

class Solution {
    public static int maxDifferenceBrute(String s) {
        int n = s.length();
        int maxDiff = 0;

        for (int i = 0; i < n; i++) {
            int zeros = 0, ones = 0;
            for (int j = i; j < n; j++) {
                if (s.charAt(j) == '0') {
                    zeros++;
                } else {
                    ones++;
                }
                maxDiff = Math.max(maxDiff, zeros - ones);
            }
        }

        return maxDiff;
    }

    public static void main(String[] args) {
        String s = "11000010001";
        System.out.println(maxDifferenceBrute(s)); // Output: 6
    }
}

Complexity Analysis

• Time Complexity: O(n^2) - two nested loops for all substrings
• Space Complexity: O(1) - only a few variables

Approach 2: Optimal

Intuition

Convert the problem to maximum subarray sum (Kadane's algorithm). Replace every '0' with +1 and every '1' with -1. Then the problem becomes: find the maximum subarray sum, which is Kadane's algorithm.

Algorithm

1. Replace '0' with +1 and '1' with -1 in the string (conceptually).
2. Apply Kadane's algorithm to find the maximum subarray sum.
3. If the result is negative or zero, no valid substring exists (return 0).

class Solution {
    public static int maxDifference(String s) {
        int n = s.length();
        int maxDiff = 0;
        int currentSum = 0;

        for (int i = 0; i < n; i++) {
            // '0' contributes +1, '1' contributes -1
            int value = (s.charAt(i) == '0') ? 1 : -1;
            currentSum += value;

            if (currentSum > maxDiff) {
                maxDiff = currentSum;
            }

            // Reset if sum goes negative (Kadane's algorithm)
            if (currentSum < 0) {
                currentSum = 0;
            }
        }

        return maxDiff;
    }

    public static void main(String[] args) {
        String s = "11000010001";
        System.out.println(maxDifference(s)); // Output: 6
    }
}

Complexity Analysis

• Time Complexity: O(n) - single pass through the string
• Space Complexity: O(1) - only a few variables used