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

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

难度中等0

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

奇偶性+找规律

• 当字符串的长度是偶数的时候:

  1. 统计当前字符串中不满足 偶数位置为1,奇数位置为0的字符的数量n1
  2. 统计当前字符串中不满足 偶数位置为0，奇数位置为1的字符的数量n2
  3. 答案就是Math.min(n1,n2)/2

• 当字符的长度是奇数的时候(数量多的那个数字一定是字符串的第一个字符):

  • 当1的数量多于0的数量的时候(此时第一个数字应当是1，此时偶数位置为1,奇数位置为0)

    • 统计当前字符串中不满足偶数位置为1，偶数位置为0的字符的数量，答案就是该数量除以2

  • 当0的数量多于1的数量的时候(此时第一个数字应当是0，此时偶数位置为0，奇数位置为1)

    • 统计当前字符串中不满足偶数位置为0,奇数位置为1的字符的数量,答案就是该数量除以2

class Solution {
    public int minSwaps(String s) {
        char[] arr = s.toCharArray();
        int n = arr.length;
        int zeroCnt = 0;
        int oneCnt = 0;
        for (int i = 0; i < n; i++) {
            if (arr[i] == '0') {
                zeroCnt++;
            } else {
                oneCnt++;
            }
        }
        if (Math.abs(oneCnt - zeroCnt) > 1) return -1;
        int cnt1 = 0, cnt2 = 0;
        int res = Integer.MAX_VALUE;
        
        if (zeroCnt <= oneCnt) {
            for (int i = 0; i < n; i++) {
                // 第一个字符是‘1’,此时偶数位置为1,奇数位置为0
                // 统计当前字符串中不满足偶数位置为1，奇数位置为0的字符的数量
                if (i % 2 == arr[i] - '0') {
                    cnt1++;
                }
            }
            res = Math.min(res, cnt1 / 2);
        }
        
        if (zeroCnt >= oneCnt) {
            for (int i = 0; i < n; i++) {
                // 第一个字符是'0'，此时偶数位置为0，奇数位置为1
                // 不满足偶数位置为0,奇数位置为1的字符的数量
                if (i % 2 != arr[i] - '0') {
                    cnt2++;
                }
            }
            res = Math.min(res, cnt2 / 2);
        }
        return res;
    }
}

赏

谢谢你请我吃糖果

微信