1888. Minimum Number of Flips to Make The Binary String Alternating - Explanation

class Solution:
    def minFlips(self, s: str) -> int:
        res = n = len(s)
        alt1, alt2 = [], []
        for i in range(n):
            alt1.append("0" if i % 2 == 0 else "1")
            alt2.append("1" if i % 2 == 0 else "0")

        def diff(A, B):
            cnt = 0
            for i in range(n):
                cnt += 1 if (A[i] != B[i]) else 0
            return cnt

        for i in range(n):
            newS = s[i:] + s[:i]
            res = min(res, min(diff(alt1, newS), diff(alt2, newS)))
        return res

class Solution:
    def minFlips(self, s: str) -> int:
        n = res = len(s)

        for i in range(n):
            start_0 = 1 if s[i] != '0' else 0
            start_1 = 1 if s[i] != '1' else 0
            c = '0'
            j = (i + 1) % n
            while j != i:
                start_1 += 1 if s[j] != c else 0
                start_0 += 1 if s[j] == c else 0
                c = '0' if c == '1' else '1'
                j = (j + 1) % n

            res = min(res, min(start_1, start_0))
        return res

class Solution:
    def minFlips(self, s: str) -> int:
        n = len(s)
        s = s + s
        alt1, alt2 = [], []
        for i in range(len(s)):
            alt1.append("0" if i % 2 == 0 else "1")
            alt2.append("1" if i % 2 == 0 else "0")

        res = len(s)
        diff1, diff2 = 0, 0
        l = 0

        for r in range(len(s)):
            if s[r] != alt1[r]:
                diff1 += 1
            if s[r] != alt2[r]:
                diff2 += 1

            if r - l + 1 > n:
                if s[l] != alt1[l]:
                    diff1 -= 1
                if s[l] != alt2[l]:
                    diff2 -= 1
                l += 1

            if r - l + 1 == n:
                res = min(res, diff1, diff2)

        return res

class Solution:
    def minFlips(self, s: str) -> int:
        res = n = len(s)
        diff1 = diff2 = l = 0

        rstart_0 = lstart_0 = '0'

        for r in range(2 * n):
            if s[r % n] != rstart_0:
                diff1 += 1
            if s[r % n] == rstart_0:
                diff2 += 1

            if r - l + 1 > n:
                if s[l] != lstart_0:
                    diff1 -= 1
                if s[l] == lstart_0:
                    diff2 -= 1
                l += 1
                lstart_0 = '1' if lstart_0 == '0' else '0'

            if r - l + 1 == n:
                res = min(res, diff1, diff2)

            rstart_0 = '1' if rstart_0 == '0' else '0'

        return res

class Solution:
    def minFlips(self, s: str) -> int:
        start_1 = 0
        for i in range(len(s)):
            if i & 1:
                start_1 += s[i] == "1"
            else:
                start_1 += s[i] == "0"

        start_0 = len(s) - start_1
        ans = min(start_0, start_1)
        if len(s) % 2 == 0:
            return ans

        dp0, dp1 = start_0, start_1
        for c in s:
            dp0, dp1 = dp1, dp0
            if c == "1":
                dp0 += 1
                dp1 -= 1
            else:
                dp0 -= 1
                dp1 += 1
            ans = min(dp0, dp1, ans)
        return ans