1864. Minimum Number of Swaps to Make the Binary String Alternating | 1601

 1class Solution:
 2    def minSwaps(self, s: str) -> int:
 3        n = len(s)
 4        swap = 0
 5        cnt = {"0": 0, "1": 0}
 6        for c in s:
 7            cnt[c] += 1
 8
 9        if abs(cnt["0"] - cnt["1"]) > 1:
10            return -1
11
12        # there're actually only several possibilities
13        # for even length
14        # 111000 -> to 010... requires [x] changes, to 101 requires [n - x] changes, answer is min(these two)/2
15
16        # for odd length, we need to focus all
17        # 01011-> more 1s than 0s -> must be 10101
18        # 11001
19        # 10101
20
21        if n % 2:  # odd
22            if cnt["1"] > cnt["0"]:
23                for idx, c in enumerate(s):
24                    if (idx % 2 == 0 and c != "1") or (idx % 2 == 1 and c != "0"):
25                        swap += 1
26            else:
27                for idx, c in enumerate(s):
28                    if (idx % 2 == 0 and c != "0") or (idx % 2 == 1 and c != "1"):
29                        swap += 1
30        else:  # even
31            swap_0 = 0  # swaps needed for 010...
32            for idx, c in enumerate(s):
33                if (idx % 2 == 0 and c != "0") or (idx % 2 == 1 and c != "1"):
34                    swap_0 += 1
35            swap = min(swap_0, n - swap_0)
36
37        return swap // 2

 1class Solution:
 2    def minSwaps(self, s: str) -> int:
 3        n = len(s)
 4        changes = 0
 5        cnt = Counter(s)
 6
 7        if abs(cnt["0"] - cnt["1"]) > 1:
 8            return -1
 9
10        if n % 2:  # odd
11            if cnt["1"] > cnt["0"]:  # 101... only
12                for idx, c in enumerate(s):
13                    if (idx % 2 == 0 and c != "1") or (idx % 2 == 1 and c != "0"):
14                        changes += 1
15            else:  # 010... only
16                for idx, c in enumerate(s):
17                    if (idx % 2 == 0 and c != "0") or (idx % 2 == 1 and c != "1"):
18                        changes += 1
19        else:  # even
20            changes_0 = 0  # changes needed for 010..., n - change_0 is for 101...
21            for idx, c in enumerate(s):
22                if (idx % 2 == 0 and c != "0") or (idx % 2 == 1 and c != "1"):
23                    changes_0 += 1
24            changes = min(changes_0, n - changes_0)
25
26        return changes // 2

 1class Solution:
 2    def minSwaps(self, s: str) -> int:
 3        n0 = s.count('0')
 4        n1 = len(s) - n0
 5        if abs(n0 - n1) > 1:
 6            return -1
 7
 8        # mismatches if pattern is 0101...
 9        mis_start0 = sum(c != ('0' if i % 2 == 0 else '1') for i, c in enumerate(s))
10        # mismatches if pattern is 1010...
11        mis_start1 = len(s) - mis_start0  # complementary in even/odd positions
12
13        if n0 == n1:
14            return min(mis_start0, mis_start1) // 2
15        elif n0 > n1:  # must start with '0'
16            return mis_start0 // 2
17        else:         # must start with '1'
18            return mis_start1 // 2