1 <= s.length <= 10^5
s[i] is either '0' or '1'.

Solution

Method 1 - Brute Force

Lets take a string "111000". The target state can be S1 - "010101" OR S2 - "101010". Now if we are allowed to just second operation i.e. Type 2, then number of flips to get to S1 OR S2 will be O(n). But we are also allowed operation Type 1, where we take prefix and append to the end of string.

Now the brute force can be we take input string, perform T2 operation, check updated string is S1 OR S2.

minimum-number-of-flips-to-make-the-binary-string-alternating-viz1.excalidraw

Method 2 - Sliding Window with Alternating Patterns

Intuition

Since we can rotate the string any number of times, we can try all possible rotations. For each rotation, we count the minimum flips needed to make the string alternating (either starting with '0' or '1'). We use a sliding window to efficiently check all rotations.

Approach

For the 1st operation T1, we can simply do

Related Tags