Skip to main content
Talentd

Maximize Active Section with Trade I - Solution & Explanation

MediumStringEnumeration9 min readAsked at: Google
Practice this problem

Problem Statement

You are given a binary string s of length n, where:

  • '1' represents an active section.
  • '0' represents an inactive section.

You can perform at most one trade to maximize the number of active sections in s. In a trade, you:

  • Convert a contiguous block of '1's that is surrounded by '0's to all '0's.
  • Afterward, convert a contiguous block of '0's that is surrounded by '1's to all '1's.

Return the maximum number of active sections in s after making the optimal trade.

Note: Treat s as if it is augmented with a '1' at both ends, forming t = '1' + s + '1'. The augmented '1's do not contribute to the final count.

 

Example 1:

Input: s = "01"

Output: 1

Explanation:

Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.

Example 2:

Input: s = "0100"

Output: 4

Explanation:

  • String "0100" → Augmented to "101001".
  • Choose "0100", convert "101001" → "100001" → "111111".
  • The final string without augmentation is "1111". The maximum number of active sections is 4.

Example 3:

Input: s = "1000100"

Output: 7

Explanation:

  • String "1000100" → Augmented to "110001001".
  • Choose "000100", convert "110001001" → "110000001" → "111111111".
  • The final string without augmentation is "1111111". The maximum number of active sections is 7.

Example 4:

Input: s = "01010"

Output: 4

Explanation:

  • String "01010" → Augmented to "1010101".
  • Choose "010", convert "1010101" → "1000101" → "1111101".
  • The final string without augmentation is "11110". The maximum number of active sections is 4.

 

Constraints:

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

Approach Overview

Problem Overview: You are given a binary string where '1' represents an active slot and '0' represents inactive. You can perform at most one trade (swap a '0' with a '1'). The goal is to maximize the length of a contiguous active section after the trade.

Approach 1: Brute Force Swap Enumeration (O(n²) time, O(1) space)

Enumerate every pair of indices where a '0' and a '1' can be swapped. After each swap, scan the string to compute the longest contiguous block of '1'. Track the maximum length observed. This approach directly simulates the allowed operation but becomes expensive because each potential swap requires another linear scan. It works for small inputs and is useful for verifying correctness of optimized approaches.

Approach 2: Enumerating Zero Positions (O(n) time, O(1) space)

Instead of simulating every swap, focus on positions of '0'. A single trade effectively turns one '0' inside a region into '1', potentially connecting two adjacent blocks of '1'. For each zero index, count the length of consecutive '1' on the left and right. The combined size represents the merged segment if that zero becomes '1'. Cap the result by the total number of '1' in the string because a swap cannot create new active slots. This linear scan strategy uses simple counting and works well when reasoning about segment merging.

Approach 3: Greedy Sliding Window (Two Pointers) (O(n) time, O(1) space)

The optimal solution treats the trade as allowing at most one '0' inside the active window. Use a sliding window with two pointers over the string. Expand the right pointer while tracking how many zeros are inside the window. If the window contains more than one zero, move the left pointer until the constraint is restored. The window length represents the longest segment achievable if one zero in the window is swapped with a '1' outside. Finally, limit the answer by the total count of '1'. This greedy approach processes each character once and naturally fits problems involving two pointers and local window constraints.

Recommended for interviews: The greedy sliding window solution is what interviewers expect. It shows you can translate a "single modification" constraint into a window condition and solve it in linear time. Discussing the brute force or zero-enumeration idea first demonstrates problem understanding, while the enumeration and two‑pointer optimization shows strong algorithmic reasoning.

Solution

The problem is essentially equivalent to finding the number of '1' characters in the string s, plus the maximum number of '0' characters in two adjacent consecutive '0' segments.

Thus, we can use two pointers to traverse the string s. Use a variable mx to record the maximum number of '0' characters in two adjacent consecutive '0' segments. We also need a variable pre to record the number of '0' characters in the previous consecutive '0' segment.

Each time, we count the number of consecutive identical characters cnt. If the current character is '1', add cnt to the answer. If the current character is '0', update mx as mx = max(mx, pre + cnt), and update pre to cnt. Finally, add mx to the answer.

Time complexity is O(n), where n is the length of the string s. Space complexity is O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Swap EnumerationO(n²)O(1)Small inputs or for validating optimized solutions
Enumerate Zero PositionsO(n)O(1)When reasoning about merging adjacent blocks of 1s
Greedy Sliding Window (Two Pointers)O(n)O(1)Best general solution for large inputs and interview settings

Video Solution

Maximize Active Section with Trade I | Simplified Approach | Dry Runs | Leetcode 3499 | MIK • codestorywithMIK • 9,016 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Maximize Active Section with Trade I easy or hard?
The problem is typically classified as Medium. The challenge is recognizing that a single trade can be modeled as allowing one zero in a contiguous window. Once that insight is clear, the implementation using two pointers becomes straightforward.
Maximize Active Section with Trade I Python/Java solution
Most implementations use the same sliding window logic regardless of language. Maintain two pointers, track how many zeros are inside the window, shrink when the constraint is violated, and update the maximum window length. The algorithm translates directly into Python, Java, C++, Go, and TypeScript.
How to solve Maximize Active Section with Trade I in O(n)?
Use a sliding window over the string while tracking the number of zeros inside the window. Allow at most one zero because one trade can replace it with a '1'. If the zero count exceeds one, move the left pointer until the window becomes valid again. Track the maximum window length and cap it by the total number of '1's in the string.
What is the best approach for Maximize Active Section with Trade I?
The best approach is a greedy sliding window using two pointers. Maintain a window that contains at most one '0', since a single trade can effectively convert one zero inside the window into '1'. Expand the right pointer and shrink the left when more than one zero appears. This produces the longest achievable active section in O(n) time and O(1) space.
Is Maximize Active Section with Trade I asked at Google/Amazon/Meta?
Problems involving longest segments after one modification frequently appear in interviews at large tech companies such as Google, Amazon, and Meta. The pattern tests sliding window reasoning and the ability to translate constraints like "one swap" or "one flip" into a window invariant.
What data structure is used in Maximize Active Section with Trade I?
The solution mainly uses a two‑pointer sliding window over a string. Only simple counters are required to track zeros and window boundaries, so no advanced data structures like heaps or trees are needed.
What is the time complexity of Maximize Active Section with Trade I?
The optimal solution runs in O(n) time because each character in the string is processed at most twice by the sliding window pointers. Space complexity is O(1) since only counters and indices are stored. Brute force approaches that simulate swaps can take O(n²) time.

Ready to solve this problem?

Practice Maximize Active Section with Trade I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Substring Without Repeating Characters

Next

Longest Palindromic Substring