709862. Split the binary string into substrings with equal number of 0s and 1s
Split the binary string into substrings with equal number of 0s and 1s
Slug: split-the-binary-string-into-substrings-with-equal-number-of-0s-and-1s
Difficulty: Easy
Id: 709862
Topic Tags: Strings, Data Structures
Company Tags: None
Summary
Given a binary string consisting of only '0's and '1's, we need to split it into substrings such that the number of '0's and '1's in each substring is equal. This problem involves manipulating strings and counting characters.
Detailed Explanation
To solve this problem, we will use a simple algorithm that iterates over the binary string and counts the number of '0's and '1's encountered so far. When the count of '0's and '1's becomes equal, we add the current substring to our result list and reset the counts.
Here is a step-by-step breakdown of the solution:
- Initialize two counters,
zeroCountandoneCount, to 0. - Iterate over the binary string:
- For each character in the string, increment the corresponding counter (either
zeroCountoroneCount). - If the counts become equal, add the current substring (from the start of the string to the current position) to our result list and reset the counts.
- For each character in the string, increment the corresponding counter (either
- After iterating over the entire string, if there are remaining characters in the string, add them as a separate substring to the result list.
Time complexity: O(n), where n is the length of the binary string. We need to iterate over the entire string once. Space complexity: O(n/2), assuming that we split the string into two equal parts on average. In the worst case, we might end up with a single substring or two very long substrings.
Optimized Solutions
Java
import java.util.ArrayList;
import java.util.List;
public class BinaryStringSplit {
public static List<String> splitBinaryString(String binaryString) {
int zeroCount = 0;
int oneCount = 0;
List<String> result = new ArrayList<>();
StringBuilder currentSubstring = new StringBuilder();
for (char c : binaryString.toCharArray()) {
if (c == '0') {
zeroCount++;
} else {
oneCount++;
}
currentSubstring.append(c);
if (zeroCount == oneCount) {
result.add(currentSubstring.toString());
zeroCount = 0;
oneCount = 0;
currentSubstring.setLength(0);
}
}
if (zeroCount > 0 || oneCount > 0) {
result.add(currentSubstring.toString());
}
return result;
}
}