Maximize Active Section with Trade I
MedPrompt
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 <= 105s[i]is either'0'or'1'
Approaches
3 approaches with complexity analysis and trade-offs.
This approach directly translates the problem's structure into code. The key insight is that the net gain from a trade is determined by the lengths of the '0' blocks adjacent to the '1' block being traded. By converting the augmented string t into a sequence of homogeneous blocks (e.g., "11001" becomes [('1', 2), ('0', 2), ('1', 1)]), we can easily identify all internal '1' blocks and their neighboring '0' blocks. We then iterate through these internal '1' blocks, calculate the potential gain for each, and find the maximum possible gain to add to the initial count of ones.
Algorithm
- Core Idea: The problem asks to maximize the number of active sections ('1's) by performing at most one trade. A trade involves swapping a block of '1's for a block of '0's. The net change in the count of '1's is
(length of '0' block gained) - (length of '1' block given up). Analyzing the trade process reveals that when we give up an internal '1' block, it merges with its two neighboring '0' blocks, creating a single large '0' block which can then be flipped to '1's. The net gain from this operation is simply the sum of the lengths of the two original neighboring '0' blocks. - Algorithm Steps:
- Construct the augmented string
t = '1' + s + '1'. This simplifies boundary conditions. - Calculate the initial number of '1's in the original string
s. - Parse the augmented string
tinto a list of contiguous blocks, storing each block's type ('0' or '1') and length. - Initialize a
maxGainvariable to 0. - Iterate through the list of blocks. For each '1' block that is not the first or the last block (i.e., it's an internal block), its neighbors must be '0' blocks.
- Calculate the potential gain for trading this '1' block, which is the sum of the lengths of its left and right neighboring '0' blocks.
- Update
maxGainwith the maximum gain found so far. - The final result is the
initialOnes + maxGain.
- Construct the augmented string
Walkthrough
import java.util.ArrayList;import java.util.List; class Solution { public int maximizeActiveSections(String s) { int n = s.length(); String t = "1" + s + "1"; int initialOnes = 0; for (char c : s.toCharArray()) { if (c == '1') { initialOnes++; } } // Group t into blocks of consecutive identical characters List<int[]> blocks = new ArrayList<>(); int p = 0; while (p < t.length()) { char type = t.charAt(p); int start = p; while (p < t.length() && t.charAt(p) == type) { p++; } // block[0] is type (0 or 1), block[1] is length blocks.add(new int[]{type - '0', p - start}); } int maxGain = 0; // An internal '1' block must have '0' blocks on both sides. // This means we need at least 3 blocks (0-1-0 pattern). if (blocks.size() < 3) { return initialOnes; } // Iterate through blocks to find internal '1' blocks for (int i = 1; i < blocks.size() - 1; i++) { // If blocks.get(i) is a '1' block, its neighbors at i-1 and i+1 must be '0' blocks. if (blocks.get(i)[0] == 1) { int gain = blocks.get(i - 1)[1] + blocks.get(i + 1)[1]; maxGain = Math.max(maxGain, gain); } } return initialOnes + maxGain; }}Complexity
Time
O(N), where N is the length of the string `s`. Calculating initial ones, building the augmented string, parsing into blocks, and iterating through the blocks all take linear time.
Space
O(N), where N is the length of the string `s`. This is because we store the augmented string `t` (O(N)) and the list of blocks, which in the worst case (e.g., "010101...") can have O(N) elements.
Trade-offs
Pros
Intuitive and directly models the problem by representing the string as a sequence of blocks.
Relatively easy to implement and understand.
Cons
Requires O(N) extra space to store the list of blocks, which can be up to N+2 blocks for a highly alternating string.
This approach uses a common dynamic programming technique to solve problems involving contiguous segments. By pre-calculating the lengths of same-character runs from both the left and the right for every position, we can quickly query the necessary information. For any potential '1' block we want to trade, we can find the lengths of its neighboring '0' blocks in O(1) time using the precomputed arrays. This avoids the overhead of creating a list of block objects and provides a systematic way to find the optimal trade.
Algorithm
- Core Idea: Instead of creating an explicit list of blocks, we can use dynamic programming with prefix and suffix style calculations to find the lengths of blocks adjacent to any point in the string.
- Algorithm Steps:
- Construct the augmented string
t = '1' + s + '1'. - Calculate the initial number of '1's in
s. - Create a
Larray of sizen+2.L[i]will store the length of the contiguous block of identical characters ending at indexi. This can be computed with a single pass from left to right. - Create a
Rarray of sizen+2.R[i]will store the length of the contiguous block of identical characters starting at indexi. This is computed with a single pass from right to left. - Initialize
maxGain = 0. - Iterate through the augmented string
t. When we find the start of an internal '1' block (a '1' preceded by a '0'), we can determine its properties. - Let the '1' block start at index
i. Its length isR[i]. The block ends atj = i + R[i] - 1. - If this '1' block is followed by a '0' (i.e., it's internal), the gain from this trade is the length of the '0' block to its left (
L[i-1]) plus the length of the '0' block to its right (R[j+1]). - Update
maxGainwith the maximum such gain found. - The final result is
initialOnes + maxGain.
- Construct the augmented string
Walkthrough
class Solution { public int maximizeActiveSections(String s) { int n = s.length(); String t = "1" + s + "1"; int nt = t.length(); int initialOnes = 0; for (char c : s.toCharArray()) { if (c == '1') { initialOnes++; } } // L[i]: length of the block of same characters ending at i int[] L = new int[nt]; L[0] = 1; for (int i = 1; i < nt; i++) { if (t.charAt(i) == t.charAt(i - 1)) { L[i] = L[i - 1] + 1; } else { L[i] = 1; } } // R[i]: length of the block of same characters starting at i int[] R = new int[nt]; R[nt - 1] = 1; for (int i = nt - 2; i >= 0; i--) { if (t.charAt(i) == t.charAt(i + 1)) { R[i] = R[i + 1] + 1; } else { R[i] = 1; } } int maxGain = 0; // Iterate to find the start of each internal '1' block for (int i = 1; i < nt - 1; i++) { if (t.charAt(i) == '1' && t.charAt(i - 1) == '0') { int len1 = R[i]; int j = i + len1 - 1; // end of the '1' block if (j + 1 < nt && t.charAt(j + 1) == '0') { int len0_left = L[i - 1]; int len0_right = R[j + 1]; maxGain = Math.max(maxGain, len0_left + len0_right); } } } return initialOnes + maxGain; }}Complexity
Time
O(N), where N is the length of `s`. Each step, including the creation of `L` and `R` arrays and the final iteration, takes linear time.
Space
O(N), where N is the length of `s`. The space is dominated by the `L` and `R` arrays and the temporary string `t`, all of which are proportional to N.
Trade-offs
Pros
Efficient O(N) time complexity.
Uses a standard dynamic programming pattern (prefix/suffix computations) that is applicable to many similar problems.
Cons
Requires O(N) extra space for the auxiliary arrays
LandR.Slightly less direct than the block grouping approach as it works on indices rather than whole blocks.
This is the most space-efficient approach. By recognizing that the calculation for a potential trade only depends on a local neighborhood of three blocks (0-1-0), we can avoid storing information about all blocks. We iterate through the string, identifying blocks on the fly. We maintain state for only the two most recently completed blocks. When we finish processing a new block, we have a window of three consecutive blocks, which is enough to determine if a valid trade is centered at the middle block and to calculate its gain. This avoids the O(N) space complexity of the previous approaches.
Algorithm
- Core Idea: We can process the string in a single pass without storing all blocks or creating large auxiliary arrays. The idea is to use a sliding window of three blocks. As we scan the string, we only need to remember the information (type and length) of the last two blocks to evaluate the current block.
- Algorithm Steps:
- Calculate the initial number of '1's in
s. - To simplify logic, we work on the augmented string
t = '1' + s + '1'. - Initialize variables to keep track of a sliding window of three blocks:
(type_m2, len_m2)for the block two steps back,(type_m1, len_m1)for the previous block, and(type_curr, len_curr)for the current block. - Iterate through
twith a pointer, identifying one block at a time. - After identifying
(type_curr, len_curr), check if the three-block window forms a0-1-0pattern. This happens iftype_m2 == '0',type_m1 == '1', andtype_curr == '0'. - If it's a match, the potential gain is
len_m2 + len_curr. UpdatemaxGainwith this value. - Slide the window: update
m2withm1's data andm1withcurr's data. - Continue until all blocks in
tare processed. - Return
initialOnes + maxGain.
- Calculate the initial number of '1's in
Walkthrough
class Solution { public int maximizeActiveSections(String s) { int n = s.length(); int initialOnes = 0; for (char c : s.toCharArray()) { if (c == '1') { initialOnes++; } } // We build string t for simpler implementation. The core logic // only needs constant extra variables. String t = "1" + s + "1"; int nt = t.length(); int maxGain = 0; int len_m2 = 0, len_m1 = 0; char type_m2 = ' ', type_m1 = ' '; // Initial empty/dummy blocks int ptr = 0; while (ptr < nt) { char type_curr = t.charAt(ptr); int start = ptr; while (ptr < nt && t.charAt(ptr) == type_curr) { ptr++; } int len_curr = ptr - start; // Check if the window of last 3 blocks is a 0-1-0 pattern if (type_m1 == '1' && type_m2 == '0' && type_curr == '0') { maxGain = Math.max(maxGain, len_m2 + len_curr); } // Slide the block window len_m2 = len_m1; type_m2 = type_m1; len_m1 = len_curr; type_m1 = type_curr; } return initialOnes + maxGain; }}Complexity
Time
O(N), as it requires a single pass through the string to identify all blocks.
Space
O(1) auxiliary space for the sliding window variables. The implementation shown uses O(N) to store the augmented string `t` for simplicity, but the algorithm itself can be implemented with true O(1) auxiliary space by handling boundary conditions of `s` directly.
Trade-offs
Pros
Most space-efficient approach, using only a constant number of variables for the core logic.
Achieves optimal O(N) time complexity.
Cons
The logic for handling the augmented boundaries and iterating through blocks can be more complex to implement correctly compared to other approaches.
The provided code creates a temporary string
tto simplify implementation, which technically uses O(N) space. A truly constant-space version would require more careful handling of string indices at the boundaries.
Solutions
Solution
class Solution {public int maxActiveSectionsAfterTrade(String s) { int n = s.length(); int ans = 0, i = 0; int pre = Integer.MIN_VALUE, mx = 0; while (i < n) { int j = i + 1; while (j < n && s.charAt(j) == s.charAt(i)) { j++; } int cur = j - i; if (s.charAt(i) == '1') { ans += cur; } else { mx = Math.max(mx, pre + cur); pre = cur; } i = j; } ans += mx; return ans; }}class Solution {public: int maxActiveSectionsAfterTrade(std ::string s) { int n = s.length(); int ans = 0, i = 0; int pre = INT_MIN, mx = 0; while (i < n) { int j = i + 1; while (j < n && s[j] == s[i]) { j++; } int cur = j - i; if (s[i] == '1') { ans += cur; } else { mx = std ::max(mx, pre + cur); pre = cur; } i = j; } ans += mx; return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.