Problem of The Day: Minimum Suffix Flips

1 min read 340 words

Problem Statement

leetcode problem link

Solution [MLE]

class Solution:
    def minFlips(self, target: str) -> int:
        curr = '0' * len(target)
        N = len(target)

        def flip(s, idx):
            arr = list(s)
            for i in range(idx, N):
                arr[i] = '0' if arr[i] == '1' else '1'
            return ''.join(arr)

        @cache
        def dp(i, s):
            if s == target:
                return 0
            if i == N:
                return float('inf')
            ans = float('inf')
            for j in range(i, N):
                take = dp(j + 1, flip(s, j)) + 1
                skip = dp(j + 1, s)
                ans = min(ans, take, skip)

            return ans

        return dp(0, curr)

Solution [Accepted]

Greey Approach

class Solution:
    def minFlips(self, target: str) -> int:
        state = "0"
        res = 0

        for b in target:
            if state != b:
                res += 1
                state = b

        return res