1864-构成交替字符串需要的最小交换次数

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:15:46 2023-09-13 16:15:46 Updated    

给你一个二进制字符串 s ，现需要将其转化为一个 交替字符串 。请你计算并返回转化所需的 最小 字符交换次数，如果无法完成转化，返回
__-1 __ 。

交替字符串 是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100"
不是。

任意两个字符都可以进行交换， 不必相邻 。

示例 1：

**输入：** s = "111000"
**输出：** 1
**解释：** 交换位置 1 和 4："1 _ **1**_ 10 _ **0**_ 0" -> "1 _ **0**_ 10 _ **1**_ 0" ，字符串变为交替字符串。

示例 2：

**输入：** s = "010"
**输出：** 0
**解释：** 字符串已经是交替字符串了，不需要交换。

示例 3：

**输入：** s = "1110"
**输出：** -1

提示：

  • 1 <= s.length <= 1000
  • s[i] 的值为 '0' 或 '1'

方法一：枚举目标字符串的形式

提示 1

符合要求的交替字符串的形式只有两种：

  1. 形如 “1010…” 的字符串，奇数位为 0'，偶数位为 1’；

  2. 形如 “0101…” 的字符串，奇数位为 1'，偶数位为 0’。

提示 2

二进制源字符串 s_1 和目标字符串 s_2 可以通过交换操作互相转化，当且仅当两个字符串中 0' 和 1’ 的个数均相等。

提示 3

假设 s_1 和 s_2 可以通过交换操作互相转化，且它们有 k 个位置不同，那么最小的交换次数为 k/2。

提示 3 解释

首先，交换 k 个字符使得新结果与原结果不同的下界为 k/2。下面我们证明这个下界是可以达到的。

不妨假设 s_1 与 s_2 中 0' 和 1’ 的个数为 n_0 与 n_1，对应下标字符分别为 i 和 j 的下标数量为 n_{ij。那么我们有

n_{00} + n_{01} = n_{00} + n_{10} = n_0,

n_{10} + n_{11} = n_{01} + n_{11} = n_1,

也就是说

n_{10} = n_{01} = k}{2}.

那么，为了使 s_1 与 s_2 一致，我们只需要将 s_1 中对应的 n_{10 个 1' 与 n_{01 个 0’ 两两交换即可。此时所需的交换次数最少，为 k/2。

思路与算法

根据 提示 1，我们枚举两种交替字符串的形式，并根据 提示 2 判断 0' 和 1’ 的个数是否相等。如果相等，我们可以计算出 s 与上述目标字符串不同的位数 diff}_1 和 diff}_2。此时根据 提示 3，对应的最少交换次数即为 diff}_1 / 2 和 diff}_2 / 2。

最终，我们取两种情况的较小值作为答案返回；若两种情况均不满足，则返回 -1。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    int minSwaps(string s) {
        int n = s.size();
        int n0 = count(s.begin(), s.end(), '0');
        int n1 = count(s.begin(), s.end(), '1');
        int res = INT_MAX;
        // "1010..."
        if (n1 == (n + 1) / 2 && n0 == n / 2){   // 不同字符个数相等
            int diff1 = 0;
            for (int i = 0; i < n; ++i){
                if (s[i] - '0' == i % 2){   // 对应位数不同
                    ++diff1;
                }
            }
            res = min(res, diff1 / 2);
        }
        // "0101..."
        if (n0 == (n + 1) / 2 && n1 == n / 2){   // 不同字符个数相等
            int diff2 = 0;
            for (int i = 0; i < n; ++i){
                if (s[i] - '0' != i % 2){   // 对应位数不同
                    ++diff2;
                }
            }
            res = min(res, diff2 / 2);
        }
        if (res == INT_MAX){
            return -1;   // 不存在
        }
        else {
            return res;
        }
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def minSwaps(self, s: str) -> int:
        n = len(s)
        n0, n1 = s.count('0'), s.count('1')
        res = float("INF")
        # "1010..."
        if n1 == (n + 1) // 2 and n0 == n // 2:   # 不同字符个数相等
            diff1 = 0
            for i in range(n):
                if int(s[i]) == i % 2:   # 对应位数不同
                    diff1 += 1
            res = min(res, diff1 // 2)
        # "0101..."
        if n0 == (n + 1) // 2 and n1 == n // 2:   # 不同字符个数相等
            diff2 = 0
            for i in range(n):
                if int(s[i]) != i % 2:   # 对应位数不同
                    diff2 += 1
            res = min(res, diff2 // 2)
        if res == float("INF"):
            return -1   # 不存在
        else:
            return res

复杂度分析

  • 时间复杂度：O(n)，其中 n 为 s 的长度。计算 n_0 与 n_1 的时间复杂度为 O(n)；每次枚举目标字符串并计算可能交换次数的时间复杂度也为 O(n)，而目标字符串共有两种。

  • 空间复杂度：O(1)，我们只使用了常数个额外变量。

 Comments
On this page
1864-构成交替字符串需要的最小交换次数