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
Are you going to make a problem out of it, so that we can test our skills?
{ minimum swaps , minimum segments}required to make the suffix(i,..,N)as good.previndicates the previous elements[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
00or11.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)Is this in O(n²) or what? If that's the case so it won't work.
Its O(2N) only