难度: Medium
给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回 -1 。
交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。
任意两个字符都可以进行交换，不必相邻 。
示例 1：
输入：s = "111000" 输出：1 解释：交换位置 1 和 4："111000" -> "101010" ，字符串变为交替字符串。
示例 2：
输入：s = "010" 输出：0 解释：字符串已经是交替字符串了，不需要交换。
示例 3：
输入：s = "1110" 输出：-1
提示：
1 <= s.length <= 1000s[i] 的值为 '0' 或 '1'运行时间: 20 ms
内存: 16.0 MB
class Solution:
def minSwaps(self, s: str) -> int:
# 统计 0 1 在奇数和偶数位置的数量
# 1 要么全在奇数位置，要么全在偶数位置
even_1, odd_1, even_0, odd_0 = 0, 0, 0, 0
for i in range(len(s)):
if i % 2 == 0:
if s[i] == '1':
even_1 += 1
else:
even_0 += 1
else:
if s[i] == '1':
odd_1 += 1
else:
odd_0 += 1
# case1: 1 在奇数，0 在偶数
if even_1 != odd_0:
ans = -1
else:
ans = even_1
# case2: 1 在偶数，0 在奇数
if odd_1 == even_0:
if ans != -1:
ans = min(ans, odd_1)
else:
ans= odd_1
return ans
为了将二进制字符串转化为交替字符串，我们可以考虑两种情况：一种是'1'在奇数位置，'0'在偶数位置；另一种是'1'在偶数位置，'0'在奇数位置。首先统计字符串中在奇数位置和偶数位置的'0'和'1'的数量。然后，根据这些统计值来判断每种情况下需要进行的交换次数。如果某种情况下的'1'的数量与对应位置的'0'的数量不匹配，则该情形不可能。如果两种情况都不可能，则返回-1。如果两种情况都可能，则选择交换次数较少的一种。
时间复杂度: O(n)
空间复杂度: O(1)
class Solution:
def minSwaps(self, s: str) -> int:
# 初始化统计变量
even_1, odd_1, even_0, odd_0 = 0, 0, 0, 0
# 遍历字符串，计算奇数和偶数位置的'1'和'0'的数量
for i in range(len(s)):
if i % 2 == 0:
if s[i] == '1':
even_1 += 1
else:
even_0 += 1
else:
if s[i] == '1':
odd_1 += 1
else:
odd_0 += 1
# 计算两种情况下的交换次数
# case1: 1 在奇数，0 在偶数
if even_1 != odd_0:
ans = -1
else:
ans = even_1
# case2: 1 在偶数，0 在奇数
if odd_1 == even_0:
if ans != -1:
ans = min(ans, odd_1)
else:
ans = odd_1
return ans
交替字符串的定义是相邻的字符必须不同。因此，只有两种模式满足这个条件：'1'在奇数位置，'0'在偶数位置；或者'1'在偶数位置，'0'在奇数位置。如果'1'和'0'都在偶数位置或者都在奇数位置，那么相邻的字符会相同，这与交替字符串的定义不符，因此这些情况不需要考虑。
对于第一种情况，'1'在奇数位置，'0'在偶数位置，奇数位置的'1'数量应该等于偶数位置的'0'数量，否则无法通过交换得到交替字符串。例如，如果奇数位置的'1'数量多于偶数位置的'0'数量，那么即使通过最优交换，也会有多余的'1'无法找到对应的'0'进行交换，因此这种情况不可能实现。
在考虑交换次数时，我们关注的是将错误位置的字符移动到正确的位置。在第一种情况（'1'在奇数位置，'0'在偶数位置），需要交换的次数等于错误位置上'1'的数量（even_1），因为每个这样的'1'都需要与一个错误位置上的'0'交换。同理，在第二种情况（'1'在偶数位置，'0'在奇数位置），需要交换的次数等于错误位置上'1'的数量（odd_1）。因此，直接使用even_1或odd_1作为交换次数是有效的。
选择交换次数较少的策略通常是有效的，因为这直接减少了操作的复杂度和可能的错误。然而，潜在的风险包括未考虑到特殊情况，比如输入字符串几乎已经是交替字符串，这时更复杂的逻辑可能会导致不必要的交换。此外，如果输入字符串长度非常大，那么即使是最小的交换次数也可能导致实际操作上的不可行。总的来说，在大多数情况下，选择交换次数较少的情况是合理和有效的。