1888. Minimum Number of Flips to Make the Binary String Alternating

1888. Minimum Number of Flips to Make the Binary String Alternating (Medium)

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

 

Constraints:

• 1 <= s.length <= 105
• s[i] is either '0' or '1'.

Companies:
Google

Related Topics:
Array, Greedy

Solution 1. DP

// OJ: https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
    int even(string &s, int c) {
        int ans = 0;
        for (int i = 0; i < s.size(); ++i) {
            ans += i % 2 ? (s[i] != c + '0') : (s[i] != '0' + (1 - c));
        }
        return ans;
    }
    int odd(string &s, int c) {
        int N = s.size();
        vector<vector<int>> dp(N + 1, vector<int>(2));
        for (int i = 0; i < s.size(); ++i) {
            dp[i + 1][1] = dp[i][1] + (i % 2 ? (s[i] != c + '0') : (s[i] != '0' + (1 - c)));
            dp[i + 1][0] = min(dp[i][1], dp[i][0]) + (i % 2 == 0? (s[i] != c + '0') : (s[i] != '0' + (1 - c)));
        }
        return min(dp[N][0], dp[N][1]);
    }
public:
    int minFlips(string s) {
        if (s.size() % 2 == 0) {
            return min(even(s, 0), even(s, 1));
        }
        return min(odd(s, 0), odd(s, 1));
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
// Ref: https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/discuss/1253874/C%2B%2B-Solution-sliding-window.-O(N)
class Solution {
public:
    int minFlips(string s) {
        int N = s.size(), c1 = 0, c2 = 0, ans = INT_MAX;
        s += s;
        string x, y;
        for (int i = 0; i < 2 * N; ++i) {
            x += i % 2 ? '1' : '0';
            y += i % 2 ? '0' : '1';
        }
        for (int i = 0; i < 2 * N; ++i) {
            if (i - N >= 0) {
                c1 -= x[i - N] != s[i - N];
                c2 -= y[i - N] != s[i - N];
            }
            c1 += x[i] != s[i];
            c2 += y[i] != s[i];
            if (i >= N - 1) ans = min({ ans, c1, c2 });
        }
        return ans;
    }
};

Solution 3.

// OJ: https://leetcode.com/problems/minimum-number-of-flips-to-make-the-binary-string-alternating/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int minFlips(string s) {
        int N = s.size(), t = 0;
        for (int i = 0; i < N; ++i) t += (s[i] == '0') ^ (i % 2 == 0);
        int ans = min(t, N - t);
        if (N % 2 == 0) return ans;
        for (int i = 0; i < N - 1; ++i) {
            t = N - t + (s[i] == '0' ? -1 : 1);
            ans = min(ans, min(t, N - t));
        }
        return ans;
    }
};