Skip to content

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

Solution 1: Sliding Window

We notice that operation \(1\) effectively turns the string into a cycle, and operation \(2\) makes a substring of length \(n\) within the cycle into an alternating binary string.

Therefore, we only need to enumerate each substring of length \(n\), calculate the cost to make it an alternating binary string, and take the minimum.

We can pre-calculate the number of differences between string \(s\) and the two types of alternating binary strings, denoted as \(\textit{cnt}\). The cost to make \(s\) into the first type of alternating binary string is \(\textit{cnt}\), and the cost to make \(s\) into the second type is \(n - \textit{cnt}\). We initialize \(\textit{ans} = \min(\textit{cnt}, n - \textit{cnt})\).

Next, we enumerate each substring of length \(n\) and update the value of \(\textit{cnt}\). For each position \(i\), we subtract the difference of \(s[i]\) from the first type of alternating binary string, and add the difference of \(s[i]\) to the second type. We update \(\textit{ans} = \min(\textit{ans}, \textit{cnt}, n - \textit{cnt})\).

Finally, return \(\textit{ans}\).

The time complexity is \(O(n)\), where \(n\) is the length of the string. The space complexity is \(O(1)\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        target = "01"
        cnt = sum(c != target[i & 1] for i, c in enumerate(s))
        ans = min(cnt, n - cnt)
        for i in range(n):
            cnt -= s[i] != target[i & 1]
            cnt += s[i] != target[(i + n) & 1]
            ans = min(ans, cnt, n - cnt)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minFlips(String s) {
        int n = s.length();
        String target = "01";
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) != target.charAt(i & 1)) {
                ++cnt;
            }
        }
        int ans = Math.min(cnt, n - cnt);
        for (int i = 0; i < n; ++i) {
            if (s.charAt(i) != target.charAt(i & 1)) {
                --cnt;
            }
            if (s.charAt(i) != target.charAt((i + n) & 1)) {
                ++cnt;
            }
            ans = Math.min(ans, Math.min(cnt, n - cnt));
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minFlips(string s) {
        int n = s.size();
        string target = "01";
        int cnt = 0;
        for (int i = 0; i < n; ++i) {
            if (s[i] != target[i & 1]) {
                ++cnt;
            }
        }
        int ans = min(cnt, n - cnt);
        for (int i = 0; i < n; ++i) {
            if (s[i] != target[i & 1]) {
                --cnt;
            }
            if (s[i] != target[(i + n) & 1]) {
                ++cnt;
            }
            ans = min({ans, cnt, n - cnt});
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
func minFlips(s string) int {
    n := len(s)
    target := "01"
    cnt := 0
    for i := range s {
        if s[i] != target[i&1] {
            cnt++
        }
    }
    ans := min(cnt, n-cnt)
    for i := range s {
        if s[i] != target[i&1] {
            cnt--
        }
        if s[i] != target[(i+n)&1] {
            cnt++
        }
        ans = min(ans, min(cnt, n-cnt))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function minFlips(s: string): number {
    const n = s.length;
    const target = '01';
    let cnt = 0;
    for (let i = 0; i < n; ++i) {
        if (s[i] !== target[i & 1]) {
            ++cnt;
        }
    }
    let ans = Math.min(cnt, n - cnt);
    for (let i = 0; i < n; ++i) {
        if (s[i] !== target[i & 1]) {
            --cnt;
        }
        if (s[i] !== target[(i + n) & 1]) {
            ++cnt;
        }
        ans = Math.min(ans, cnt, n - cnt);
    }
    return ans;
}

 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
impl Solution {
    pub fn min_flips(s: String) -> i32 {
        let n: usize = s.len();
        let bytes = s.as_bytes();
        let target = b"01";
        let mut cnt: i32 = 0;

        for i in 0..n {
            if bytes[i] != target[i & 1] {
                cnt += 1;
            }
        }

        let mut ans = cnt.min(n as i32 - cnt);

        for i in 0..n {
            if bytes[i] != target[i & 1] {
                cnt -= 1;
            }
            if bytes[i] != target[(i + n) & 1] {
                cnt += 1;
            }
            ans = ans.min(cnt).min(n as i32 - cnt);
        }

        ans
    }
}

 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
/**
 * @param {string} s
 * @return {number}
 */
var minFlips = function (s) {
    const n = s.length;
    const target = '01';
    let cnt = 0;
    for (let i = 0; i < n; ++i) {
        if (s[i] !== target[i & 1]) {
            ++cnt;
        }
    }
    let ans = Math.min(cnt, n - cnt);
    for (let i = 0; i < n; ++i) {
        if (s[i] !== target[i & 1]) {
            --cnt;
        }
        if (s[i] !== target[(i + n) & 1]) {
            ++cnt;
        }
        ans = Math.min(ans, cnt, n - cnt);
    }
    return ans;
};

 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
public class Solution {
    public int MinFlips(string s) {
        int n = s.Length;
        string target = "01";
        int cnt = 0;

        for (int i = 0; i < n; ++i) {
            if (s[i] != target[i & 1]) {
                ++cnt;
            }
        }

        int ans = Math.Min(cnt, n - cnt);

        for (int i = 0; i < n; ++i) {
            if (s[i] != target[i & 1]) {
                --cnt;
            }
            if (s[i] != target[(i + n) & 1]) {
                ++cnt;
            }
            ans = Math.Min(ans, Math.Min(cnt, n - cnt));
        }

        return ans;
    }
}

Comments