1864. Minimum Number of Swaps to Make the Binary String Alternating

by

1864. Minimum Number of Swaps to Make the Binary String Alternating

Medium

Given a binary string s, return the minimum number of character swaps to make it alternating, or -1 if it is impossible.

The string is called alternating if no two adjacent characters are equal. For example, the strings "010" and "1010" are alternating, while the string "0100" is not.

Any two characters may be swapped, even if they are not adjacent.

Example 1:

Input: s = "111000"
Output: 1
Explanation: Swap positions 1 and 4: "111000" -> "101010"
The string is now alternating.

Example 2:

Input: s = "010"
Output: 0
Explanation: The string is already alternating, no swaps are needed.

Example 3:

Input: s = "1110"
Output: -1

Constraints:

  • 1 <= s.length <= 1000
  • s[i] is either '0' or '1'.

思路

给定长度的 alternating string 有两种可能：”0101..” 或 “1010..”。

对每一种可能的 alternating string，统计 s 与其在多少个位置上不一致（0 和 1 分别统计），得到 wrong_0s 和 wrong_1s。若 wrong_0s == wrong_1s，则此情况下的 minSwap 即为 wrong_0s；否则为 -1。

对于两种可能的 alternating string，分别计算结果。若其中一个为 -1，返回另一个；否则返回两者中较小的。

int _minSwaps(const string &s, const bool start_with) {
    char char01[2] = {'0', '1'};
    int wrong_0s = 0;
    int wrong_1s = 0;
    bool idx = start_with;
    for (auto c_iter = s.begin(), end_iter = s.end(); c_iter != end_iter; ++c_iter, idx = !idx) {
        if (*c_iter != char01[idx]) {
            if (idx) {
                ++wrong_0s;
            } else {
                ++wrong_1s;
            }
        }
    }
    return wrong_0s == wrong_1s ? wrong_0s : -1;
}

class Solution {
public:
    int minSwaps(string s) {
        int min_swap_0 = _minSwaps(s, 0);
        int min_swap_1 = _minSwaps(s, 1);
        if (min_swap_0 == -1) {
            return min_swap_1;
        } else if (min_swap_1 == -1) {
            return min_swap_0;
        } else {
            return min_swap_0 < min_swap_1 ? min_swap_0 : min_swap_1;
        }
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Minimum Number of Swaps to Make the Binary String Alternating.

Memory Usage: 6.6 MB, less than 59.22% of C++ online submissions for Minimum Number of Swaps to Make the Binary String Alternating.

Leave a Comment