317. Maximum Difference of Zeros and Ones in a Binary String

Given a binary string, find the maximum value of (count of 0s minus count of 1s) over every contiguous, non-empty substring. Print -1 if the string contains no 0s at all.

Input: A single line contains the binary string s. Output: Print a single integer - the maximum value of (count of 0s minus count of 1s) over any contiguous substring, or -1 if s has no 0s.

1 <= |s| <= 10^5

The all-1s special case (printing -1) must be checked explicitly BEFORE running Kadane's - without this check, Kadane's would just return the least-negative single element, which isn't the semantically correct 'impossible' answer this problem requires.

Find the maximum value of (count of 0s minus count of 1s) over any contiguous substring of a binary string. Brute force: Check every possible substring directly, counting 0s and 1s and computing the difference - this costs O(n²), too slow for large strings, when the Kadane's-on-mapped-values technique achieves the same in O(n). Optimised: Mapping '0' to +1 and '1' to -1 transforms 'maximize (zeros - ones) over a substring' directly into 'maximize the sum over a subarray' - exactly what Kadane's algorithm solves, letting this string-counting problem reuse a well-known array technique with zero modification beyond the initial value mapping.

For every pair of start and end indices (i, j) defining a substring, count the zeros and ones within it directly by scanning the substring, compute zeros minus ones, and keep the running maximum over all substrings. This checks every possible substring exhaustively as the problem defines, but re-scanning each substring from scratch is very wasteful. Time: O(n^3) (O(n^2) substrings, O(n) to score each) Space: O(1) extra

Precompute a prefix array where prefix[i] = (count of 0s - count of 1s) among the first i characters, in one O(n) pass. Now the score of any substring (i, j) is just prefix[j] - prefix[i-1], computed in O(1). Iterating over all O(n^2) pairs (i, j) and taking the best score using this O(1) lookup removes the O(n) rescanning cost per substring, though the number of substrings considered is still quadratic. Time: O(n^2) Space: O(n)

Map each '0' to +1 and each '1' to -1, and observe the problem becomes exactly 'maximum sum contiguous subarray', solvable with Kadane's algorithm in a single left-to-right pass: maintain the best sum ending at the current position (extend the previous run or restart at the current element, whichever is larger) and track the overall best. This avoids ever looking at pairs of indices at all, collapsing the search to one linear scan; a special check for 'no zeros in the string' handles the -1 edge case separately. Time: O(n) Space: O(1)

1. If the string is ALL 1s, immediately print -1 - no substring can have a positive or zero count of 0s. 2. Otherwise, MAP each '0' to +1 and each '1' to -1, then the answer is simply the MAXIMUM-SUM CONTIGUOUS SUBARRAY (Kadane's algorithm) over that mapped sequence. 3. Kadane's here must allow a SINGLE-element subarray as the minimum window, resetting the running current value whenever continuing would make it smaller than starting fresh.

Time: O(n) - one mapping pass, plus one Kadane's pass. Space: O(1) extra space beyond a couple of running trackers (or O(n) if the mapped array is materialized explicitly, though this isn't necessary).

Test a string of all 1s (must print -1), a string of all 0s (answer equals the string's length), and |s| = 10^5 (upper bound) for the O(n) Kadane's-algorithm approach.

Be ready to explain the value-mapping trick explicitly (0->+1, 1->-1) - recognizing that a 'count difference' problem can often be transformed into a 'maximum subarray sum' problem via a clever value substitution is a broadly reusable technique.