How do I know if the binary string can be alternated?

A binary string can only be alternated if the number of '0's and '1's differ by at most 1. If the difference is greater than 1, it's impossible to alternate the string.

What are the two valid alternating binary strings?

The two valid alternating binary strings are '010101...' and '101010...', which alternate between '0' and '1'.

What is the approach to solve the Minimum Number of Swaps to Make the Binary String Alternating?

The approach involves checking the number of mismatches against the two alternating patterns and calculating the minimum swaps needed based on these mismatches.

Can any two characters in the string be swapped?

Yes, any two characters can be swapped, even if they are not adjacent, to make the string alternating.

What should I do if the string is already alternating?

If the string is already alternating, no swaps are needed, and the answer is 0.

#1864

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

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

给你一个二进制字符串 s ，现需要将其转化为一个交替字符串。请你计算并返回转化所需的最小字符交换次数，如果无法完成转化，返回 -1 。交替字符串是指：相邻字符之间不存在相等情况的字符串。例如，字符串 "010" 和 "1010" 属于交替字符串，但 "0100" 不是。任意两个字符都可…

字符串贪心

题目描述

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

lightbulb

解题思路

方法一：计数

我们先统计字符串 $\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

13

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)

speed

复杂度分析

指标	值
时间	complexity depends on the approach for checking mismatches against the two alternating patterns, with an optimal solution typically having O(n) time complexity where n is the string length. The space complexity is O(1) since no additional space is needed beyond counters and indices.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Checks the candidate's ability to use greedy methods for string manipulation problems.
question_mark
Evaluates the candidate's understanding of balancing and invariants in algorithms.
question_mark
Assesses whether the candidate can validate edge cases like impossible transformations.

warning

常见陷阱

外企场景

error
Forgetting to check if the number of '0's and '1's are balanced, which would make it impossible to alternate the string.
error
Overcomplicating the solution by using nested loops or additional data structures where a greedy approach suffices.
error
Not correctly counting mismatches for both alternating patterns before calculating the swaps.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Given a larger binary string, how would your approach scale in terms of time and space complexity?
arrow_right_alt
How can you optimize for different problem constraints, such as limiting the number of swaps or providing feedback on swap validity?
arrow_right_alt
What happens if the string has an even number of characters, but still cannot be made alternating?

help

常见问题

外企场景

继续练习

#1850 邻位交换的最小次数 #1881 插入后的最大值 #1903 字符串中的最大奇数