What is the maximum binary string after change?

The maximum binary string is the result of repeatedly transforming '01' pairs into '10', until no more transformations can be made, resulting in a string with at most one '0'.

How does the greedy approach work in this problem?

The greedy approach focuses on iterating through the string and applying the '01' to '10' transformation as often as possible to push zeros toward the end, maximizing the binary string's value.

What is the time complexity of solving the problem?

The time complexity depends on the approach used. In the optimal case, it can be O(n), but in some implementations, it might reach O(n^2).

Can this problem be solved using dynamic programming?

Although dynamic programming could be used for some problems in string manipulation, this problem is best solved with a greedy approach due to the simplicity of the operations and the fact that each transformation can be applied directly to maximize the string value.

What happens if the binary string is already maximized?

If the binary string is already maximized, no operations will be needed, and the string remains unchanged. The algorithm should handle this efficiently without unnecessary steps.

#1702

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

修改后的最大二进制字符串

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。比方说， " 00 010" -> " 10 010" 操作 2 ：如果二进制串包含子字符串 "10" ，你可…

字符串贪心

题目描述

给你一个二进制字符串 binary ，它仅有 0 或者 1 组成。你可以使用下面的操作任意次对它进行修改：

操作 1 ：如果二进制串包含子字符串 "00" ，你可以用 "10" 将其替换。
- 比方说， "00010" -> "10010"
操作 2 ：如果二进制串包含子字符串 "10" ，你可以用 "01" 将其替换。
- 比方说， "00010" -> "00001"

请你返回执行上述操作任意次以后能得到的 最大二进制字符串 。如果二进制字符串 x 对应的十进制数字大于二进制字符串 y 对应的十进制数字，那么我们称二进制字符串 x 大于二进制字符串 y 。

示例 1：

输入：binary = "000110"
输出："111011"
解释：一个可行的转换为：
"000110" -> "000101" 
"000101" -> "100101" 
"100101" -> "110101" 
"110101" -> "110011" 
"110011" -> "111011"

示例 2：

输入：binary = "01"
输出："01"
解释："01" 没办法进行任何转换。

提示：

1 <= binary.length <= 10⁵
binary 仅包含 '0' 和 '1' 。

lightbulb

解题思路

方法一：脑筋急转弯

我们观察发现，操作 $2$ 可以把所有的 $1$ 都移动到字符串的末尾，而操作 $1$ 可以把所有的 0000..000 串变为 111..110。

因此，要想得到最大的二进制串，我们应该把所有不在开头的 $1$ 移动到字符串末尾，使得字符串变为 111..11...000..00..11 的形式，然后借助操作 $1$ 把中间的 000..00 变为 111..10。这样我们最终可以得到一个最多包含一个 $0$ 的二进制字符串，这个字符串就是我们要求的最大二进制串。

在代码实现上，我们首先判断字符串是否包含 $0$ ，如果不包含，直接返回原字符串。否则，我们找到第一个 $0$ 的位置 $k$ ，加上该位置之后的 $0$ 的个数，得到的就是修改后的字符串的 $0$ 所在的位置，其余位置都是 $1$ 。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是字符串的长度。

1

2

3

4

5

6

7

8

class Solution:
    def maximumBinaryString(self, binary: str) -> str:
        k = binary.find('0')
        if k == -1:
            return binary
        k += binary[k + 1 :].count('0')
        return '1' * k + '0' + '1' * (len(binary) - k - 1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Evaluate understanding of greedy algorithms in string manipulation.
question_mark
Look for the candidate's ability to handle edge cases, such as no valid operations or already maximized strings.
question_mark
Assess their ability to optimize time complexity and avoid unnecessary operations.

warning

常见陷阱

外企场景

error
Failing to recognize that only one zero can remain in the string after transformations.
error
Not validating the string structure after each operation and missing potential '01' pairs to change.
error
Overcomplicating the solution by applying unnecessary operations or using suboptimal approaches.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if you were allowed to apply the operation multiple times in a row for the same '01' pair?
arrow_right_alt
How would the solution change if you had to ensure the resulting string contains at least one '1'?
arrow_right_alt
Can this approach be adapted to other string manipulation problems with different operations?

help

常见问题

外企场景

继续练习

#1689 十-二进制数的最少数目 #1717 删除子字符串的最大得分 #1736 替换隐藏数字得到的最晚时间