What is the core pattern behind this problem?

The core pattern revolves around identifying and manipulating zero-one segments in a binary string to maximize the number of active sections.

How can I approach maximizing the active sections?

Split the string into segments and evaluate where a trade can increase the number of sections. Focus on flipping '0' blocks surrounded by '1's.

Why is it important to focus on zero-one segments?

Zero-one segments allow you to understand the structure of the string and identify where trades will create the most impact on the number of active sections.

Can the string consist only of '1's or '0's?

Yes, if the string is entirely '1's or '0's, the maximum number of active sections will remain constant, and no trade will be possible.

How does GhostInterview help with problem-solving here?

GhostInterview provides hints and step-by-step guidance to break down the problem into smaller segments, making it easier to spot potential optimizations and avoid common pitfalls.

#3499

Medium

auto_awesomestring·结合·enumeration

LeetCode 题解工作台

操作后最大活跃区段数 I

给你一个长度为 n 的二进制字符串 s ，其中： '1' 表示一个活跃区段。 '0' 表示一个非活跃区段。你可以执行最多一次操作来最大化 s 中的活跃区段数量。在一次操作中，你可以：将一个被 '0' 包围的连续 '1' 区块转换为全 '0' 。然后，将一个被 '1' 包围的连续 '…

字符串枚举

题目描述

给你一个长度为 n 的二进制字符串 s，其中：

'1' 表示一个活跃区段。
'0' 表示一个 非活跃 区段。

你可以执行 最多一次操作 来最大化 s 中的活跃区段数量。在一次操作中，你可以：

将一个被 '0' 包围的连续 '1' 区块转换为全 '0'。
然后，将一个被 '1' 包围的连续 '0' 区块转换为全 '1'。

返回在执行最优操作后，s 中的最大活跃区段数。

注意：处理时需要在 s 的两侧加上 '1' ，即 t = '1' + s + '1'。这些加上的 '1' 不会影响最终的计数。

示例 1：

输入： s = "01"

输出： 1

解释：

因为没有被 '0' 包围的 '1' 区块，因此无法进行有效操作。最大活跃区段数为 1。

示例 2：

输入： s = "0100"

输出： 4

解释：

字符串 "0100" → 两端加上 '1' 后得到 "101001" 。
选择 "0100"，"101001" → "100001" → "111111" 。
最终的字符串去掉两端的 '1' 后为 "1111" 。最大活跃区段数为 4。

示例 3：

输入： s = "1000100"

输出： 7

解释：

字符串 "1000100" → 两端加上 '1' 后得到 "110001001" 。
选择 "000100"，"110001001" → "110000001" → "111111111"。
最终的字符串去掉两端的 '1' 后为 "1111111"。最大活跃区段数为 7。

示例 4：

输入： s = "01010"

输出： 4

解释：

字符串 "01010" → 两端加上 '1' 后得到 "1010101"。
选择 "010"，"1010101" → "1000101" → "1111101"。
最终的字符串去掉两端的 '1' 后为 "11110"。最大活跃区段数为 4。

提示：

1 <= n == s.length <= 10⁵
s[i] 仅包含 '0' 或 '1'

lightbulb

解题思路

方法一：贪心 + 双指针

题目实际上等价于求字符串 $\textit{s}$ 中，字符 '1' 的数量，再加上相邻两个连续的字符 '0' 串中 ``'0'` 的最大数量。

因此，我们可以使用双指针来遍历字符串 $\textit{s}$ ，用一个变量 $\textit{mx}$ 来记录相邻两个连续的字符 '0' 串中 '0' 的最大数量。我们还需要一个变量 $\textit{pre}$ 来记录上一个连续的字符 '0' 串的数量。

每一次，我们统计当前连续相同字符的数量 $\textit{cnt}$ ，如果当前字符为 '1'，则将 $\textit{cnt}$ 加入到答案中；如果当前字符为 '0'，则将 $\textit{mx}$ 更新为 $\textit{mx} = \max(\textit{mx}, \textit{pre} + \textit{cnt})$ ，并将 $\textit{pre}$ 更新为 $\textit{cnt}$ 。最后，我们将答案加上 $\textit{mx}$ 即可。

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

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        n = len(s)
        ans = i = 0
        pre, mx = -inf, 0
        while i < n:
            j = i + 1
            while j < n and s[j] == s[i]:
                j += 1
            cur = j - i
            if s[i] == "1":
                ans += cur
            else:
                mx = max(mx, pre + cur)
                pre = cur
            i = j
        ans += mx
        return ans

speed

复杂度分析

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

psychology

面试官常问的追问

外企场景

question_mark
The candidate identifies key segments of '0's and '1's and their potential for creating additional sections.
question_mark
They analyze the impact of different trade scenarios on the string's structure.
question_mark
They demonstrate an efficient approach to evaluating and maximizing the number of active sections.

warning

常见陷阱

外企场景

error
Not correctly identifying segments of '0's and '1's for potential trades.
error
Assuming that any '0' block can be flipped, when only '0' blocks surrounded by '1's are relevant.
error
Overcomplicating the problem by attempting to perform unnecessary trades that don’t increase the number of sections.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Consider cases where the string consists entirely of '0's or '1's.
arrow_right_alt
Handle strings with mixed lengths of '0's and '1's, ensuring the trade maximizes sections.
arrow_right_alt
Analyze larger inputs where performance optimizations become more critical.

help

常见问题

外企场景

继续练习

#3503 子字符串连接后的最长回文串 I #3445 奇偶频次间的最大差值 II #3435 最短公共超序列的字母出现频率