题目描述
给你一个二进制字符串 s
,现需要将其转化为一个 交替字符串。请你计算并返回转化所需的 最小 字符交换次数,如果无法完成转化,返回 -1
。
交替字符串 是指:相邻字符之间不存在相等情况的字符串。例如,字符串 "010"
和 "1010"
属于交替字符串,但 "0100"
不是。
任意两个字符都可以进行交换,不必相邻。
样例
输入:s = "111000"
输出:1
解释:交换位置 1 和 4:"111000" -> "101010" ,字符串变为交替字符串。
输入:s = "010"
输出:0
解释:字符串已经是交替字符串了,不需要交换。
输入:s = "1110"
输出:-1
限制
1 <= s.length <= 1000
s[i]
的值为'0'
或'1'
。
算法
(分类讨论) $O(n)$
- 分两类讨论,一类是以
0
开头的字符串,一类是以1
开头的字符串。 - 分别求出两类字符串所需要的交换次数。
- 求交换次数可以记录下
0 -> 1
以及1 -> 0
的次数,然后进行比较看是否相等。
时间复杂度
- 遍历字符串两次,故总时间复杂度度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储临时字符串。
C++ 代码
class Solution {
private:
int solve(string s, char first) {
const int n = s.size();
int cnt[2];
cnt[0] = cnt[1] = 0;
if (s[0] != first) {
s[0] = first;
cnt[first - '0']++;
}
for (int i = 1; i < n; i++) {
if (s[i] != s[i - 1]) continue;
s[i] = '1' - s[i - 1] + '0';
cnt[s[i] - '0']++;
}
return cnt[0] == cnt[1] ? cnt[0] : INT_MAX;
}
public:
int minSwaps(string s) {
const int n = s.size();
int res = solve(s, '0');
res = min(res, solve(s, '1'));
if (res == INT_MAX)
return -1;
return res;
}
};
想请教一下大佬,这题如果是只能交换相邻的两个字符,应该怎么做呢
大佬记得把O(n²)改成O(n)
done