跳转至

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

题目描述

给你一个二进制字符串 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'

解法

方法一：计数

我们先统计字符串 \(\textit{s}\) 中字符 \(0\) 和字符 \(1\) 的个数，分别记为 \(n_0\) 和 \(n_1\)。

如果 \(n_0\) 和 \(n_1\) 的绝对值大于 \(1\)，那么无法构成交替字符串，返回 \(-1\)。

如果 \(n_0\) 和 \(n_1\) 相等，那么我们可以分别计算将字符串转化为以 \(0\) 开头和以 \(1\) 开头的交替字符串所需要的交换次数，取最小值。

如果 \(n_0\) 和 \(n_1\) 不相等，那么我们只需要计算将字符串转化为以字符个数较多的字符开头的交替字符串所需要的交换次数。

问题转换为：计算字符串 \(\textit{s}\) 转化为以字符 \(c\) 开头的交替字符串所需要的交换次数。

我们定义一个函数 \(\text{calc}(c)\)，表示将字符串 \(\textit{s}\) 转化为以字符 \(c\) 开头的交替字符串所需要的交换次数。我们遍历字符串 \(\textit{s}\)，对于每个位置 \(i\)，如果 \(i\) 与 \(c\) 的奇偶性不同，那么我们需要交换这个位置的字符，计数器 \(+1\)。由于每次交换都会使两个位置的字符变得相同，因此最终的交换次数为计数器的一半。

时间复杂度 \(O(n)\)，其中 \(n\) 是字符串 \(\textit{s}\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def minSwaps(self, s: str) -> int:
        def calc(c: int) -> int:
            return sum((c ^ i & 1) != x for i, x in enumerate(map(int, s))) // 2

        n0 = s.count("0")
        n1 = len(s) - n0
        if abs(n0 - n1) > 1:
            return -1
        if n0 == n1:
            return min(calc(0), calc(1))
        return calc(0 if n0 > n1 else 1)

 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
class Solution {
    private char[] s;

    public int minSwaps(String s) {
        this.s = s.toCharArray();
        int n1 = 0;
        for (char c : this.s) {
            n1 += (c - '0');
        }
        int n0 = this.s.length - n1;
        if (Math.abs(n0 - n1) > 1) {
            return -1;
        }
        if (n0 == n1) {
            return Math.min(calc(0), calc(1));
        }
        return calc(n0 > n1 ? 0 : 1);
    }

    private int calc(int c) {
        int cnt = 0;
        for (int i = 0; i < s.length; ++i) {
            int x = s[i] - '0';
            if ((i & 1 ^ c) != x) {
                ++cnt;
            }
        }
        return cnt / 2;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int minSwaps(string s) {
        int n0 = ranges::count(s, '0');
        int n1 = s.size() - n0;
        if (abs(n0 - n1) > 1) {
            return -1;
        }
        auto calc = [&](int c) -> int {
            int cnt = 0;
            for (int i = 0; i < s.size(); ++i) {
                int x = s[i] - '0';
                if ((i & 1 ^ c) != x) {
                    ++cnt;
                }
            }
            return cnt / 2;
        };
        if (n0 == n1) {
            return min(calc(0), calc(1));
        }
        return calc(n0 > n1 ? 0 : 1);
    }
};

 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
func minSwaps(s string) int {
    n0 := strings.Count(s, "0")
    n1 := len(s) - n0
    if abs(n0-n1) > 1 {
        return -1
    }
    calc := func(c int) int {
        cnt := 0
        for i, ch := range s {
            x := int(ch - '0')
            if i&1^c != x {
                cnt++
            }
        }
        return cnt / 2
    }
    if n0 == n1 {
        return min(calc(0), calc(1))
    }
    if n0 > n1 {
        return calc(0)
    }
    return calc(1)
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function minSwaps(s: string): number {
    const n0 = (s.match(/0/g) || []).length;
    const n1 = s.length - n0;
    if (Math.abs(n0 - n1) > 1) {
        return -1;
    }
    const calc = (c: number): number => {
        let cnt = 0;
        for (let i = 0; i < s.length; i++) {
            const x = +s[i];
            if (((i & 1) ^ c) !== x) {
                cnt++;
            }
        }
        return Math.floor(cnt / 2);
    };
    if (n0 === n1) {
        return Math.min(calc(0), calc(1));
    }
    return calc(n0 > n1 ? 0 : 1);
}

 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
/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function (s) {
    const n0 = (s.match(/0/g) || []).length;
    const n1 = s.length - n0;
    if (Math.abs(n0 - n1) > 1) {
        return -1;
    }
    const calc = c => {
        let cnt = 0;
        for (let i = 0; i < s.length; i++) {
            const x = +s[i];
            if (((i & 1) ^ c) !== x) {
                cnt++;
            }
        }
        return Math.floor(cnt / 2);
    };
    if (n0 === n1) {
        return Math.min(calc(0), calc(1));
    }
    return calc(n0 > n1 ? 0 : 1);
};

评论