1888. 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.

Example 1:

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".

Example 2:

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

Example 3:

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

#include <iostream>
#include <cstring>

class Solution {
public:
    int minFlips(std::string s) {
        int n = s.length();
        int num1 = 0, num2 = 0, k = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] == k + '0') {
                ++num1;
            }
            else {
                ++num2;
            }
            k = 1 - k;
        }
        int min1 = num1;
        int min2 = num2;
        if (n % 2 == 0) {
            return std::min(min1, min2);
        }
        
        for (int i = 0; i < n; ++i) {
            if (s[i] == k + '0') {
                --num2;
                ++num1;
            }
            else {
                --num1;
                ++num2;
            }
            k = 1 - k;
            min1 = std::min(min1, num1);
            min2 = std::min(min2, num2);
        }
        return std::min(min1, min2);
    }
};