thetwoface's blog

Minimum number of Identical even Subsegments of a Binary String in minimum bit flips.
By thetwoface, history, 9 months ago, In English

Given a binary string s, the objective is to divide it into subsegments such that all bits into that segment is identical(i.e. either '0' or '1') and the subsegments should be of even length. Mathematically for any subsegment Bi ∈ s ⇒ len(Bi)%2==0 and ∀ j either Bij='0' or '1' . The criteria to achieve this: 1. This should be done in minimum number of flips required to form an Identical even subsegments. 2. And Minimize the total number of subsegments. Outpur the minimum number of subsegments.

NOTE: First you have to minimize the number of flips before minimizing subsegments.

Constraints are: 2<= s.size() <=10^5

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Are you going to make a problem out of it, so that we can test our skills?

→ Reply
»
9 months ago, hide # |
← Rev. 3  
Vote: I like it 0 Vote: I do not like it
  • Observation: Every pair of characters $$$(2i-1 , 2i)$$$ are the same in a good string, that is, $$$s[1] = s[2] , s[3] = s[4]$$$ , .... in the final modified string.
  • We can process them in groups of 2.
  • If n%2 == 1 , never possible
  • Lets define $$$dp[i][prev]$$$ = pair of { minimum swaps , minimum segments} required to make the suffix (i,..,N) as good. prev indicates the previous element s[i-1] value.

  • By this definition of dp, we can do transitions to solve the problem. For every adjacent pair, we only have 2 cases 00 or 11.


Transitions:


- case0.first = (s[i] == 1) + (s[i+1] == 1) + dp[i+2][0].first
- case0.second = (prev == 1) + dp[i+2][0].second
- case1.first = (s[i] == 0) + (s[i+1] == 0) + dp[i+2][1].first
- case1.second = (prev == 0) + dp[i+2][1].second
- dp[i][prev] = min( case0 , case 1)

→ Reply