Split the Binary string into two substring with equal 0s and 1s
Problem Statement
Given a binary string consisting only of '0's and '1's, split the string into the maximum number of substrings such that each substring has an equal number of 0s and 1s. Return the count of maximum splits possible, or -1 if not possible.
Example:
-
Input:
"0100110101" -
Output:
4 -
Explanation: "01", "0011", "01", "01" - each has equal 0s and 1s
-
Input:
"0111100010" -
Output:
3 -
Explanation: "011110001", "0" is not valid. Valid split: "01", "111000", "10"
-
Input:
"0110" -
Output:
2 -
Explanation: "01", "10"
-
Input:
"1001" -
Output:
2 -
Explanation: "10", "01"
Approach 1: Count Difference
Intuition
Traverse the string and keep track of the difference between count of 0s and 1s. Whenever the counts become equal (difference = 0), we found a valid split point.
Algorithm
- Initialize counters for 0s and 1s (or use a single counter for difference)
- Traverse the string character by character
- Increment/decrement counter based on '0' or '1'
- When counter becomes 0, increment split count
- Return split count, or -1 if counter is not 0 at the end
public class Solution {
public int maxSplits(String s) {
int count0 = 0, count1 = 0;
int splits = 0;
for (char c : s.toCharArray()) {
if (c == '0') {
count0++;
} else {
count1++;
}
// Equal counts mean valid split point
if (count0 == count1) {
splits++;
count0 = 0;
count1 = 0;
}
}
// If counts are not equal at the end, split is not possible
if (count0 != count1) {
return -1;
}
return splits;
}
// Using single counter
public int maxSplitsOptimized(String s) {
int balance = 0;
int splits = 0;
for (char c : s.toCharArray()) {
balance += (c == '0') ? 1 : -1;
if (balance == 0) {
splits++;
}
}
return (balance == 0) ? splits : -1;
}
}Complexity Analysis
- Time Complexity: O(n) - Single pass through the string
- Space Complexity: O(1) - Only using counters
Approach 2: Print the Substrings
Intuition
Not only count the splits but also print/store the actual substrings.
import java.util.*;
public class Solution {
public List<String> splitBinaryString(String s) {
List<String> result = new ArrayList<>();
int balance = 0;
int start = 0;
for (int i = 0; i < s.length(); i++) {
balance += (s.charAt(i) == '0') ? 1 : -1;
if (balance == 0) {
result.add(s.substring(start, i + 1));
start = i + 1;
}
}
// Check if valid split
if (balance != 0) {
return new ArrayList<>(); // Empty list indicates not possible
}
return result;
}
}Approach 3: Check Prerequisites First
Intuition
Before attempting to split, verify that splitting is possible by checking if total 0s equals total 1s.
public class Solution {
public int maxSplitsWithCheck(String s) {
// First check if total 0s equals total 1s
int total0 = 0, total1 = 0;
for (char c : s.toCharArray()) {
if (c == '0') total0++;
else total1++;
}
if (total0 != total1) {
return -1;
}
// Now count splits
int balance = 0;
int splits = 0;
for (char c : s.toCharArray()) {
balance += (c == '0') ? 1 : -1;
if (balance == 0) {
splits++;
}
}
return splits;
}
}Edge Cases
Variation: Minimum Splits
Intuition
The minimum number of splits is always 1 if the string is valid (total 0s = total 1s).
Key Takeaways
- Balance tracking is the key insight - treat '0' as +1 and '1' as -1 (or vice versa)
- When balance becomes 0, we found a valid split point
- Total 0s must equal total 1s for any valid split to exist
- The algorithm naturally finds the maximum number of splits (greedy)
- Time complexity is O(n) with single pass
- This technique is similar to finding balanced parentheses
- Edge cases: empty string, all same characters, odd length strings
Related Problems
- Maximum Score After Splitting a String
- Split a String in Balanced Strings
- Minimum Flips to Make a OR b Equal to c