Minimum Number Of Flips To Make The Binary String Alternating - Leetcode Solution

Problem Description: You are given a binary string s consisting of 0's and 1's. You can flip a character i.e. convert 0 to 1 or 1 to 0 at any position of the string. We need to find the minimum number of flips required to make the string alternate, i.e. every two adjacent characters should be different.

Example 1: Input: s = "0100" Output: 1 Explanation: We can flip the last digit to get "0101"

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

Approach: We can use brute force approach to flip each digit and check whether the alternate condition is satisfied. It will take O(n^2) time complexity and hence is not recommended for large strings. A better approach is as follows:

• First, we need to count how many flips are required to make the string start with '0', i.e. alternate between '0' and '1' starting with '0'. For example, if the string is "1010", then the required number of flips would be '1', as we can flip the first '1' to '0'.
• Similarly, we need to count the number of flips required to make the string start with '1', i.e. alternate between '0' and '1' starting with '1'. For example, if the string is "0101", then the required number of flips would be '1', as we can flip the first '0' to '1'.
• The minimum number of flips required can be calculated as the minimum of the above two values.

Algorithm:

1. Initialize two values, zeroFirst and oneFirst, to count the number of flips required to make the string alternate and start with '0' or '1' respectively.
2. Iterate over the input string s and check whether each character is in the alternating position. If not, increment the corresponding counter. For example, if the index is even and the character is '1', then increment the zeroFirst counter as it should be '0' at even position.
3. Return the minimum of zeroFirst and oneFirst as this would give the minimum flips required to make the string alternate.

Time Complexity: O(n) Space Complexity: O(1)

Code:

class Solution { public: int minFlips(string s) { int zeroFirst = 0, oneFirst = 0; for(int i=0; i<s.size(); i++) { if((i%2==0 && s[i]=='1') || (i%2==1 && s[i]=='0')) // check for alternating positions zeroFirst++; else if((i%2==0 && s[i]=='0') || (i%2==1 && s[i]=='1')) // check for alternating positions oneFirst++; } return min(zeroFirst, oneFirst); } };

1