将s转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数,如果无法完成转化,返回 -1 。
class Solution:
def minSwaps(self, s: str) -> int:
cnt1 = 0
odd1 = 0
cnt0 = 0
n = len(s)
for i in range(n):
if s[i] == '1':
cnt0 += 1
else:
cnt1 += 1
if i % 2 == 0:
odd1 += 1
if abs(cnt0 - cnt1) > 1:
return -1
ans = 0
if n % 2 == 0: #偶数个,则看看第一位是0还是1,第一位决定了奇数位置上需要交换的个数
ans = min(odd1, n // 2 - odd1)
else:
if cnt0 > cnt1: # 如果0的个数>1的个数,则0一定要在奇数位置上,才能满足交替,所以此时的交换次数就是:在奇数位置上的1的个数
ans = odd1
else: #否则看看不在奇数位上的1的个数
ans = cnt1 - odd1
return ans