Maximize Active Section with Trade I — Problem & Solution
Maximize Active Section with Trade I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Maximize Active Section with Trade I is a medium coding problem on strings and enumeration, asked in Google interviews.
- Difficulty: Medium
- Topics: Strings, Enumeration
- Asked at: Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given a binary string s of length n, where '1' marks an active section and '0' an inactive one.
You may perform at most one trade. A trade is two steps, done in order:
- pick a contiguous block of
'1's that is surrounded by'0's on both sides and turn all of it into'0's; - then pick a contiguous block of
'0's that is surrounded by'1's on both sides and turn all of it into'1's.
For the purpose of the trade only, treat s as if it had an extra '1' at each end (t = '1' + s + '1'); those two added characters are never counted.
Return the maximum number of '1's that s can contain after the best choice.
Example 1
Input: s = "01"
Output: 1
Explanation: No block of '1's is surrounded by '0's, so no trade is possible.
Example 2
Input: s = "0100"
Output: 4
Explanation: With t = "101001", zero the middle '1' to get "100001", then fill the zero block to get "111111": all 4 characters of s are '1'.
Example 3
Input: s = "1000100"
Output: 7
Explanation: t = "110001001". Zero the lone '1' between the zero blocks ("110000001"), then fill them all: every character of s becomes '1'.
Constraints
1 <= n == s.length <= 10^5s[i] is either '0' or '1'
Hints for Maximize Active Section with Trade I
Hint 1
Step 1 can only remove a block of
'1's that has a block of'0's directly on each side — it merges those two zero blocks into one big block.Hint 2
Step 2 should then fill that merged block: you lose the removed ones but gain them back, plus both zero blocks.
Hint 3
So the gain is the sum of two consecutive zero blocks. Take the best such pair and add it to the number of
'1's already ins; with fewer than two zero blocks no trade helps.
How to solve Maximize Active Section with Trade I
Removing a '1' block that separates zero blocks of sizes z1 and z2 creates one zero block of size z1 + o + z2, and filling it gives back the o ones plus z1 + z2 new ones. So a trade gains the sum of two adjacent zero blocks; the answer is the count of ones plus the best adjacent pair.
Approach
- Count the
'1's ins. - Scan
sfor its maximal blocks of'0's, in order, remembering the length of the previous block. - For each block after the first, update
best = max(best, previous + current). - Return
ones + best(beststays 0 when there are fewer than two zero blocks).
Why it works
In the augmented string any '1' block surrounded by zeros lies between two consecutive zero blocks of s. After removing it, filling the merged block gains z1 + z2; filling any other zero block z gains z - o < z, and z itself is part of some adjacent pair whose sum is at least z. Hence the best trade gains exactly the largest adjacent-pair sum, and not trading gains 0.
Complexity
- Time —
O(n) - Space —
O(1)
Pitfalls
- A
'1'block touching either end ofsis next to the augmented'1', not a'0', so it cannot be removed. - The augmented
'1's are never counted in the answer. - Two zero blocks are always separated by a
'1'block, so consecutive zero blocks in a scan are exactly the pairs a trade can merge.
Reference solution
Python
def maxActiveSectionsAfterTrade(s: str) -> int:
ones = s.count("1")
best, prev = 0, -1
n, i = len(s), 0
while i < n:
if s[i] == "1":
i += 1
continue
j = i
while j < n and s[j] == "0":
j += 1
cur = j - i
if prev >= 0:
best = max(best, prev + cur)
prev = cur
i = j
return ones + bestJava
public static int maxActiveSectionsAfterTrade(String s) {
int n = s.length(), ones = 0, best = 0, prev = -1, i = 0;
for (int k = 0; k < n; k++) if (s.charAt(k) == '1') ones++;
while (i < n) {
if (s.charAt(i) == '1') { i++; continue; }
int j = i;
while (j < n && s.charAt(j) == '0') j++;
int cur = j - i;
if (prev >= 0) best = Math.max(best, prev + cur);
prev = cur;
i = j;
}
return ones + best;
}C++
int maxActiveSectionsAfterTrade(string s) {
int n = s.size(), ones = 0, best = 0, prev = -1, i = 0;
for (char c : s) if (c == '1') ones++;
while (i < n) {
if (s[i] == '1') { i++; continue; }
int j = i;
while (j < n && s[j] == '0') j++;
int cur = j - i;
if (prev >= 0) best = max(best, prev + cur);
prev = cur;
i = j;
}
return ones + best;
}JavaScript
var maxActiveSectionsAfterTrade = function(s) {
var n = s.length, ones = 0, best = 0, prev = -1, i = 0;
for (var k = 0; k < n; k++) if (s[k] === "1") ones++;
while (i < n) {
if (s[i] === "1") { i++; continue; }
var j = i;
while (j < n && s[j] === "0") j++;
var cur = j - i;
if (prev >= 0 && prev + cur > best) best = prev + cur;
prev = cur;
i = j;
}
return ones + best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings