I was trying to split a binary string such that each substring has the same number of 1's and 0's. By this I mean, given a string like 0010110010, it can be split into 00101 10010 with both substrings having 2 ones and 3 zeros. Could anyone point me to something similar. Sorry, I don't have any code to share.

CodePudding user response：

Say a given string can be split into n substrings that meet the condition, each of which has a 0's and b 1's. Guess what? All the substrings must have the same length (== a b)! Therefore the search space is very limited:

1. You try to divide the length of the original string by 2,3,4...(int)string.length()/2. Only divisors without a remainder could be a valid one. For example, you have string 010010010, you can't divide it into 2 substrings and let both substrings have the equal number of 0's and 1's because 9/2=4 R 1.
2. You just try divisors one by one. Say dividing the original string into n two-character long substrings then I can check if substrings[0], substring[1]...have the same number of 0's and 1's...

If you only need one solution, the time complexity should be no more than o(n^2)

CodePudding user response：

• N substrings of the number of ones K1 and zeros K0, means substrings of the same length.
• The entire string must be of length N*(K1 K0).
• Also the entire string must have N*K1 ones and N*K0 zeros.
• So you can count all ones, NK1, derive the zeroes count NK0, and N is a factor of the gcd(NK1, NK0). (Greatest Common Divisor is a simple algorithm.)
• There is always a solution: the repetition of 1 substring.

Of course we do not solve tasks here.