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 <= 1000
  • s[i] 是 ‘0’ 或 ‘1’

提示：

  • 考虑长度为 n 的所有有效字符串
  • 尝试计算与每个长度为 n 的有效字符串不匹配的位置数量

解题思路

解题思路

对于一个交替的二进制字符串，只有两种可能的模式：

  1. 以 ‘0’ 开头：010101…
  2. 以 ‘1’ 开头：101010…

我们需要检查原字符串能否通过交换变成这两种模式中的任意一种。

核心观察：

  • 交替字符串中，‘0’ 和 ‘1’ 的数量最多相差 1
  • 如果字符串长度为偶数，‘0’ 和 ‘1’ 的数量必须相等
  • 如果字符串长度为奇数，‘0’ 和 ‘1’ 的数量相差 1

算法步骤：

  1. 统计原字符串中 ‘0’ 和 ‘1’ 的数量
  2. 检查是否满足交替字符串的数量约束条件
  3. 分别计算变成两种模式所需的交换次数
  4. 返回较小的交换次数

交换次数计算： 对于每种模式，我们只需要统计不匹配的位置数。由于每次交换可以修复两个不匹配的位置，所以交换次数 = 不匹配位置数 / 2。

这是一个贪心算法，因为我们总是选择交换次数更少的方案。

代码实现

class Solution {
public:
    int minSwaps(string s) {
        int n = s.length();
        int count0 = 0, count1 = 0;
        
        // 统计0和1的数量
        for (char c : s) {
            if (c == '0') count0++;
            else count1++;
        }
        
        // 检查是否可能形成交替字符串
        if (abs(count0 - count1) > 1) {
            return -1;
        }
        
        // 计算两种模式的交换次数
        int swaps1 = 0, swaps2 = 0;
        
        // 模式1: 以0开头 (0101...)
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && s[i] != '0') swaps1++;
            else if (i % 2 == 1 && s[i] != '1') swaps1++;
        }
        
        // 模式2: 以1开头 (1010...)
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && s[i] != '1') swaps2++;
            else if (i % 2 == 1 && s[i] != '0') swaps2++;
        }
        
        // 只有当对应模式可能时才考虑
        int result = INT_MAX;
        if (count0 >= count1) result = min(result, swaps1 / 2);
        if (count1 >= count0) result = min(result, swaps2 / 2);
        
        return result;
    }
};

class Solution:
    def minSwaps(self, s: str) -> int:
        n = len(s)
        count0 = s.count('0')
        count1 = s.count('1')
        
        # 检查是否可能形成交替字符串
        if abs(count0 - count1) > 1:
            return -1
        
        # 计算两种模式的交换次数
        swaps1 = 0  # 模式1: 以0开头 (0101...)
        swaps2 = 0  # 模式2: 以1开头 (1010...)
        
        for i in range(n):
            if i % 2 == 0:
                if s[i] != '0':
                    swaps1 += 1
                if s[i] != '1':
                    swaps2 += 1
            else:
                if s[i] != '1':
                    swaps1 += 1
                if s[i] != '0':
                    swaps2 += 1
        
        # 只有当对应模式可能时才考虑
        result = float('inf')
        if count0 >= count1:
            result = min(result, swaps1 // 2)
        if count1 >= count0:
            result = min(result, swaps2 // 2)
        
        return result

public class Solution {
    public int MinSwaps(string s) {
        int n = s.Length;
        int count0 = 0, count1 = 0;
        
        // 统计0和1的数量
        foreach (char c in s) {
            if (c == '0') count0++;
            else count1++;
        }
        
        // 检查是否可能形成交替字符串
        if (Math.Abs(count0 - count1) > 1) {
            return -1;
        }
        
        // 计算两种模式的交换次数
        int swaps1 = 0, swaps2 = 0;
        
        // 模式1: 以0开头 (0101...)
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && s[i] != '0') swaps1++;
            else if (i % 2 == 1 && s[i] != '1') swaps1++;
        }
        
        // 模式2: 以1开头 (1010...)
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0 && s[i] != '1') swaps2++;
            else if (i % 2 == 1 && s[i] != '0') swaps2++;
        }
        
        // 只有当对应模式可能时才考虑
        int result = int.MaxValue;
        if (count0 >= count1) result = Math.Min(result, swaps1 / 2);
        if (count1 >= count0) result = Math.Min(result, swaps2 / 2);
        
        return result;
    }
}

/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function(s) {
    const n = s.length;
    let count0 = 0, count1 = 0;
    
    // 统计0和1的数量
    for (let i = 0; i < n; i++) {
        if (s[i]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O(n)
空间复杂度O(1)

其中 n 是字符串的长度。我们需要遍历字符串几次来统计字符数量和计算不匹配位置，每次遍历都是 O(n) 时间。空间复杂度为常数级别，只使用了几个变量来存储计数和交换次数。