CODEWITHSUNDEEP
algorithmbinarysubstringcombinationspermutation
murage kibicho
murage kibicho

Reputation: 644

Split binary string such that every substring has the same number of 1's and 0's

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.

Upvotes: 0

Views: 717

Answers (2)

Joop Eggen
Joop Eggen

Reputation: 109557

  • 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.

Upvotes: 1

user2379740
user2379740

Reputation:

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)

Upvotes: 2

Related Questions