Question

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

English Version

题目描述

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

解法

方法一

class Solution:
  def minSwaps(self, s: str) -> int:
    s0n0 = s0n1 = s1n0 = s1n1 = 0
    for i in range(len(s)):
      if (i & 1) == 0:
        if s[i] != '0':
          s0n0 += 1
        else:
          s1n1 += 1
      else:
        if s[i] != '0':
          s1n0 += 1
        else:
          s0n1 += 1
    if s0n0 != s0n1 and s1n0 != s1n1:
      return -1
    if s0n0 != s0n1:
      return s1n0
    if s1n0 != s1n1:
      return s0n0
    return min(s0n0, s1n0)

class Solution {
  public int minSwaps(String s) {
    int s0n0 = 0, s0n1 = 0;
    int s1n0 = 0, s1n1 = 0;
    for (int i = 0; i < s.length(); ++i) {
      if ((i & 1) == 0) {
        if (s.charAt(i) != '0') {
          s0n0 += 1;
        } else {
          s1n1 += 1;
        }
      } else {
        if (s.charAt(i) != '0') {
          s1n0 += 1;
        } else {
          s0n1 += 1;
        }
      }
    }
    if (s0n0 != s0n1 && s1n0 != s1n1) {
      return -1;
    }
    if (s0n0 != s0n1) {
      return s1n0;
    }
    if (s1n0 != s1n1) {
      return s0n0;
    }
    return Math.min(s0n0, s1n0);
  }
}

/**
 * @param {string} s
 * @return {number}
 */
var minSwaps = function (s) {
  let n = s.length;
  let n1 = [...s].reduce((a, c) => parseInt(c) + a, 0);
  let n0 = n - n1;
  let count = Infinity;
  let half = n / 2;
  // 101、1010
  if (n1 == Math.ceil(half) && n0 == Math.floor(half)) {
    let cur = 0;
    for (let i = 0; i < n; i++) {
      if (i % 2 == 0 && s.charAt(i) != '1') cur++;
    }
    count = Math.min(count, cur);
  }
  // 010、0101
  if (n0 == Math.ceil(half) && n1 == Math.floor(half)) {
    let cur = 0;
    for (let i = 0; i < n; i++) {
      if (i % 2 == 0 && s.charAt(i) != '0') cur++;
    }
    count = Math.min(count, cur);
  }
  return count == Infinity ? -1 : count;
};