What is the optimal approach for solving Maximum Number of Operations to Move Ones to the End?

The optimal approach uses a greedy strategy where you perform the operation on the leftmost '1' each time to maximize the number of operations.

How do I ensure the greedy choice is valid in this problem?

By selecting the leftmost '1' and swapping it with the nearest '0' to its right, you maximize the number of valid operations. This greedy choice maintains the desired invariant.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the binary string, as you traverse the string once to perform the swaps.

Are there any edge cases I should consider?

Yes, consider cases where the string has no '1's or all '1's are already at the end, in which no operations can be performed.

How can GhostInterview help with this problem?

GhostInterview provides detailed insights into using greedy algorithms and optimizing the solution for time and space complexity, ensuring an efficient solution.

#3228

Medium

auto_awesome贪心·invariant

LeetCode 题解工作台

将 1 移动到末尾的最大操作次数

给你一个二进制字符串 s 。你可以对这个字符串执行任意次下述操作：选择字符串中的任一下标 i （ i + 1 ），该下标满足 s[i] == '1' 且 s[i + 1] == '0' 。将字符 s[i] 向右移直到它到达字符串的末端或另一个 '1' 。例如，对于 s = "0100…

字符串贪心计数

题目描述

给你一个二进制字符串 s。

你可以对这个字符串执行 任意次 下述操作：

选择字符串中的任一下标 i（ i + 1 < s.length ），该下标满足 s[i] == '1' 且 s[i + 1] == '0'。
将字符 s[i] 向右移直到它到达字符串的末端或另一个 '1'。例如，对于 s = "010010"，如果我们选择 i = 1，结果字符串将会是 s = "000110"。

返回你能执行的最大操作次数。

示例 1：

输入： s = "1001101"

输出： 4

解释：

可以执行以下操作：

选择下标 i = 0。结果字符串为 s = "0011101"。
选择下标 i = 4。结果字符串为 s = "0011011"。
选择下标 i = 3。结果字符串为 s = "0010111"。
选择下标 i = 2。结果字符串为 s = "0001111"。

示例 2：

输入： s = "00111"

输出： 0

提示：

1 <= s.length <= 10⁵
s[i] 为 '0' 或 '1'。

lightbulb

解题思路

方法一：贪心

我们用一个变量 $\textit{ans}$ 记录答案，用一个变量 $\textit{cnt}$ 记录当前的 $1$ 的个数。

然后我们遍历字符串 $s$ ，如果当前字符是 $1$ ，则 $\textit{cnt}$ 加一，否则如果存在前一个字符，且前一个字符是 $1$ ，那么前面的 $\textit{cnt}$ 个 $1$ 可以往后移动，答案加上 $\textit{cnt}$ 。

最后返回答案即可。

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

1

2

3

4

5

6

7

8

9

10

class Solution:
    def maxOperations(self, s: str) -> int:
        ans = cnt = 0
        for i, c in enumerate(s):
            if c == "1":
                cnt += 1
            elif i and s[i - 1] == "1":
                ans += cnt
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate demonstrates an understanding of greedy algorithms by explaining the choice of selecting the leftmost '1'.
question_mark
The candidate should discuss the trade-offs of swapping earlier versus later '1's, as this maximizes operations.
question_mark
The candidate should be able to articulate the time and space complexity for their solution.

warning

常见陷阱

外企场景

error
Misunderstanding the operation by performing swaps in non-greedy orders, reducing the number of valid operations.
error
Not considering edge cases where no operations are possible, such as when all '1's are already at the end of the string.
error
Failing to optimize for time complexity when implementing the solution, leading to inefficient algorithms.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling strings with only '0's or only '1's.
arrow_right_alt
Allowing a fixed number of operations rather than maximizing the count.
arrow_right_alt
Changing the operation such that you can only swap a fixed number of '1's.

help

常见问题

外企场景

继续练习

#3085 成为 K 特殊字符串需要删除的最少字符数 #3081 替换字符串中的问号使分数最小 #3035 回文字符串的最大数量