1888. Minimum Number of Flips to Make the Binary String Alternating - cocoder39/coco39_LC GitHub Wiki

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

Option 1: DP

find an index i such that s[0 : i+1] are appended to the end of s. As a result, s[i+1] -> s[-1] -> s[0] -> s[i] are alternating

class Solution:
    def minFlips(self, s: str) -> int:    
        # min flips to make alternating string with s[-1] == val
        def helper(val):
            # n-1 -> n-2 -> .. -> 0 are alternating
            dp1 = [0] * n
            dp1[-1] = 0 if s[-1] == val else 1
            
            for i in range(n-2, -1, -1):
                if (n - 1 - i) % 2 == 0:
                    dp1[i] = dp1[i+1] + (0 if s[i] == val else 1)
                else:
                    dp1[i] = dp1[i+1] + (0 if s[i] != val else 1)
             
            # n-1 -> 0 -> 1 > .. -> n-2 are alternating
            dp2 = [0] * n
            dp2[-1] = 0 if s[0] == val else 1
            dp2[0] = 0 if s[0] != val else 1
            for i in range(1, n-1):
                if i % 2 == 0:
                    dp2[i] = dp2[i-1] + (0 if s[i] != val else 1)
                else:
                    dp2[i] = dp2[i-1] + (0 if s[i] == val else 1)
            
            res = dp1[0]
            for i in range(n-1):
                res = min(res, dp1[i+1] + dp2[i])
            return res
        
        n = len(s)
        return min(helper('0'), helper('1'))
        

Option 2: sliding window

source = s + s then the problem is to finding a length of n window in source

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        target = []
        for i in range(2 * n):
            if i % 2 == 0:
                target.append('0')
            else:
                target.append('1')
        
        source = s + s
        flip0, flip1 = 0, 0
        res = float("inf")
        for i, ch in enumerate(source):
            if ch != target[i]:
                flip0 += 1
            else:
                flip1 += 1
            
            if i >= n:
                if source[i-n] != target[i-n]:
                    flip0 -= 1
                else:
                    flip1 -= 1
            
            if i >= n - 1:
                res = min(res, flip0, flip1)
        
        return res