LC-1888 Medium LeetCode

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

String Dynamic Programming Greedy Sliding Window

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 40% Topics: String, Dynamic Programming, Greedy, Sliding Window

Reading material

Strings 12 min 1-D Dynamic Programming 16 min Greedy 11 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(1)

class Solution(object):
    def minFlips(self, s):
        """
        :type s: str
        :rtype: int
        """
        result = float("inf")
        cnt1 = cnt2 = 0
        for i in xrange(2*len(s)-1 if len(s)%2 else len(s)):
            if i >= len(s):
                cnt1 -= int(s[i%len(s)])^((i-len(s))%2)^0
                cnt2 -= int(s[i%len(s)])^((i-len(s))%2)^1
            cnt1 += int(s[i%len(s)])^(i%2)^0
            cnt2 += int(s[i%len(s)])^(i%2)^1
            if i >= len(s)-1:
                result = min(result, cnt1, cnt2)
        return result

Solution from kamyu104/LeetCode-Solutions · MIT