README_EN.md

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

中文文档

Description

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

Solutions

Python3

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        target = '01'
        cnt = 0
        for i, c in enumerate(s):
            cnt += c != target[i & 1]
        res = min(cnt, n - cnt)
        for i in range(n):
            cnt -= s[i] != target[i & 1]
            cnt += s[i] != target[(i + n) & 1]
            res = min(res, cnt, n - cnt)
        return res

Java

class Solution {
    public int minFlips(String s) {
        int n = s.length();
        String target = "01";
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            cnt += (s.charAt(i) == target.charAt(i & 1) ? 0 : 1);
        }
        int res = Math.min(cnt, n - cnt);
        for (int i = 0; i < n; ++i) {
            cnt -= (s.charAt(i) == target.charAt(i & 1) ? 0 : 1);
            cnt += (s.charAt(i) == target.charAt((i + n) & 1) ? 0 : 1);
            res = Math.min(res, Math.min(cnt, n - cnt));
        }
        return res;
    }
}

TypeScript

function minFlips(s: string): number {
    const n: number = s.length;
    const target: string[] = ['0', '1'];
    let count: number = 0;
    for (let i: number = 0; i < n; ++i) {
        count += s.charAt(i) == target[i & 1] ? 0 : 1;
    }
    let res = Math.min(count, n - count);
    for (let i: number = 0; i < n; ++i) {
        count -= s.charAt(i) == target[i & 1] ? 0 : 1;
        count += s.charAt(i) == target[(i + n) & 1] ? 0 : 1;
        res = Math.min(res, count, n - count);
    }
    return res;
}

...