Minimum Number of Flips to Make the Binary String Alternating — LeetCode 1888 Python Solution

The problem

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.

Example

Input

s = "111000"

Output

2

Explanation

Use the first operation two times to make s = "100011".

Python solution

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

Complexity

Pattern: Sliding Window

Collapse a nested loop over every subarray into a single pass with two indices. LeetCode 1888. Minimum Number of Flips to Make the Binary String Alternating is filed here because LeetCode tags it Sliding Window, which is the vocabulary this hub collects.

The sliding window guide has the Python template for the pattern and the 116 LeetCode problems that use it.

Related problems