Sliding Window - Minimum Number of Flips to Make the Binary String Alternating

You are given a binary string s. You are allowed to perform two types of operations on the string in any sequence:

Type-1: Remove the character at the start of the string s and append it to the end of the string.
Type-2: Pick any character in s and flip its value, i.e., if its value is '0' it becomes '1' and vice-versa.

Return the minimum number of type-2 operations you need to perform such that s becomes alternating.

The string is called alternating if no two adjacent characters are equal.

For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Input: s = "111000"
Output: 2
Explanation: Use the first operation two times to make s = "100011".
Then, use the second operation on the third and sixth elements to make s = "101010".

Input: s = "010"
Output: 0
Explanation: The string is already alternating.

Input: s = "1110"
Output: 1
Explanation: Use the second operation on the second element to make s = "1010".

Constraints:

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

Solution 1 - Using sliding window technique, check minimum changes needed in one of the alternate strings, one starts with '0' and other starts with '1'

The intution of of this approach is that, say we apply Type-1 operation on every single character in input string, for example input string is "111000":

After removing first character, remove 1 from the beginning and adding it at end, input string will become "110001"
Apply the same on second character, remove 1 from the beginning and adding it at end, input string will become "100011"
Apply the same on third character, remove 1 from the beginning and adding it at end, input string will become "000111"
Apply the same on fourth character, remove 0 from the beginning and adding it at end, input string will become "001110"
Apply the same on fifth character, remove 0 from the beginning and adding it at end, input string will become "011100"
Apply the same on sixth character, remove 0 from the beginning and adding it at end, input string will become "111000"

As you notice, when you apply Type-1 operation on all characters, we will get the same input string.

In terms of alternate strings possible, there are only two possible strings with alternate characters, one starts with '0' and the other starts with '1', in the above example with input string of length 6, alternate strings can be either "010101" or "101010".

So, in this approach, we are going to concatenate input string twice, "111000111000" and also take two alternate string with this length, 010101010101 and 101010101010, the reason we are doing this is because, when we have to try applying on Type -1 operation on every single single character, it will end up with the same string again, so, using this concatenated string we can look at a window length of 6. For e.g.:

In first iteration, we can consider input string as is "111000111000".
In next iteration, we can consider input string as if first character is removed from beginning and added at the and "111000111000".

Similarly, continue for next iterations, now we can check how many Type -2 operations would be needed to convert this to either of alternate strings at the same window length, and take the minimum of these 2.

Implementation steps:

First, take the length of input string s, and store it in a variable n, because of this is going to be our window length.
Next, modify input string, i.e. concatenate the same string at the end s = s + s.
Next, prepare two alternate strings with same length as modified input string s, call them alternate1 and alternate2, one starts with '0' and the other starts with '1' (for example, in the input string s length is 6, then alternate strings lengths would be 12)
Next, create five variables left, right that we will use to adjust the window, diff1 to store minimum flips needed if we have to produce alternate1 string, diff2 to store minimum flips needed if we have to produce alternate2 string, and ans to store the answer, initialize ans with maximum value as modified s length since we are anyway going to find the minimum flips required.
Next, run a while loop until right pointer reaches end of string s, and do the following:
- Check the character at right pointer between s and alternate1, if they are not same increment diff1, similarly check the character at right pointer between s and alternate1, if they are not same increment diff2, by doing so we are capturing whether a flip is needed to turn input string into one of the alternate string or not.
- Next, check if we are going out of bounds, i.e. if our window length going beyond n (original input string length) right - left + 1 > n, if it is then move the left pointer, also check character at left pointer between s and alternate1, if they are not same, decrement diff1, similarly check character at left pointer between s and alternate2, if they are not same, decrement diff2. The reason we have to decrement is, if the characters were not same, we would have incremented earlier.
- When the window size is exactly n, i.e. right - left + 1 == n, take the minimum between diff1 and diff2 and update the ans.
- At the end of while loop increment right pointer to move to the next element in string s.
Finally, return ans.

public class MinimumNumberOfFlipsToMakeTheBinaryStringAlternate { static int minFlips(String s) { //111000 - if we apply type-1 operation, i.e. remove character from beginning and add it at end. //to apply for all characters, that means until we get the same string back, 111000 -> 111000 // In this approach, we will take the whole string as if we apply type-1 on every character 111000111000 // then apply sliding window with length as 6 and see how many type-2 operations are required to get one of the possible // alternate string, one starts with 1 and another starts with 0. int n= s.length(); s = s+ s; StringBuilder alternate1= new StringBuilder(); StringBuilder alternate2= new StringBuilder(); // First let's construct the two possible alternate strings for(int i=0; i<s.length(); i++) { if(i%2==0){ alternate1.append("0"); alternate2.append("1"); } else { alternate1.append("1"); alternate2.append("0"); } } // now apply sliding window int left = 0; int right=0; int diff1 =0; int diff2 =0; int ans = s.length();//we are going to find min, so setting it to max possible while(right < s.length()) { if(s.charAt(right) != alternate1.charAt(right)){ diff1++; } if(s.charAt(right) != alternate2.charAt(right)) { diff2++; } if(right - left +1 >n) { if(s.charAt(left) != alternate1.charAt(left)) { diff1--; } if(s.charAt(left) != alternate2.charAt(left)) { diff2--; } left++; } //update ans, only if the window size is n, that is because, we want to know how many // flips needed to alternate the string with original size. if(right - left +1 == n) { ans = Math.min(ans, Math.min(diff1, diff2)); } right++; } return ans; } public static void main(String[] args) { System.out.println(minFlips("01001001101")); System.out.println(minFlips("111000")); System.out.println(minFlips("010")); System.out.println(minFlips("1110")); } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time, where n is the length of input string s.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Constraints:

Contents

Implementation steps:

Complexity Analysis: