Maximize Active Section with Trade I
MediumUpdated: Aug 2, 2025
Practice on:
Problem
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.
Examples
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 `"10 _**1**_ 001"` -> `"1 _**0000**_ 1"` -> `"1 _**1111**_ 1"`.
* 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 `"11000 _**1**_ 001"` -> `"11 _**000000**_ 1"` -> `"11 _**111111**_ 1"`.
* 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 `"10 _**1**_ 0101"` -> `"1 _**000**_ 101"` -> `"1 _**111**_ 101"`.
* The final string without augmentation is `"11110"`. The maximum number of active sections is 4.
Constraints
1 <= n == s.length <= 10^5s[i]is either'0'or'1'
Solution
Method 1 – Enumerate All Possible Trades
Intuition
We want to maximize the number of active sections by performing at most one trade, which consists of removing a block of '1's (surrounded by '0's) and then flipping a block of '0's (surrounded by '1's). By simulating all possible valid trades, we can find the optimal result.
Approach
- Augment the string:
t = '1' + s + '1'. - Find all blocks of '1's surrounded by '0's and all blocks of '0's surrounded by '1's in
t. - For each possible pair (remove a '1' block, flip a '0' block), simulate the trade:
- Remove the '1' block (set to '0'), then flip the '0' block (set to '1').
- Count the number of '1's in the resulting string (excluding the augmented ends).
- Track the maximum.
- If no valid trade, return the count of '1's in
s.
Code
C++
class Solution {
public:
int maximizeActiveSections(string s) {
string t = "1" + s + "1";
int n = t.size();
vector<pair<int,int>> ones, zeros;
int i = 0;
while (i < n) {
if (t[i] == '1' && t[i-1] == '0') {
int j = i;
while (j < n && t[j] == '1') j++;
if (t[j] == '0') ones.push_back({i, j-1});
i = j;
} else if (t[i] == '0' && t[i-1] == '1') {
int j = i;
while (j < n && t[j] == '0') j++;
if (t[j] == '1') zeros.push_back({i, j-1});
i = j;
} else {
i++;
}
}
int ans = count(s.begin(), s.end(), '1');
for (auto& o : ones) {
for (auto& z : zeros) {
string tmp = t;
for (int k = o.first; k <= o.second; ++k) tmp[k] = '0';
for (int k = z.first; k <= z.second; ++k) tmp[k] = '1';
int cnt = 0;
for (int k = 1; k < n-1; ++k) if (tmp[k] == '1') cnt++;
ans = max(ans, cnt);
}
}
return ans;
}
};
Go
func maximizeActiveSections(s string) int {
t := "1" + s + "1"
n := len(t)
ones, zeros := [][2]int{}, [][2]int{}
for i := 0; i < n; {
if t[i] == '1' && t[i-1] == '0' {
j := i
for j < n && t[j] == '1' { j++ }
if t[j] == '0' { ones = append(ones, [2]int{i, j-1}) }
i = j
} else if t[i] == '0' && t[i-1] == '1' {
j := i
for j < n && t[j] == '0' { j++ }
if t[j] == '1' { zeros = append(zeros, [2]int{i, j-1}) }
i = j
} else {
i++
}
}
ans := 0
for _, c := range s {
if c == '1' { ans++ }
}
for _, o := range ones {
for _, z := range zeros {
tmp := []byte(t)
for k := o[0]; k <= o[1]; k++ { tmp[k] = '0' }
for k := z[0]; k <= z[1]; k++ { tmp[k] = '1' }
cnt := 0
for k := 1; k < n-1; k++ { if tmp[k] == '1' { cnt++ } }
if cnt > ans { ans = cnt }
}
}
return ans
}
Java
class Solution {
public int maximizeActiveSections(String s) {
String t = "1" + s + "1";
int n = t.length();
List<int[]> ones = new ArrayList<>(), zeros = new ArrayList<>();
int i = 0;
while (i < n) {
if (t.charAt(i) == '1' && t.charAt(i-1) == '0') {
int j = i;
while (j < n && t.charAt(j) == '1') j++;
if (t.charAt(j) == '0') ones.add(new int[]{i, j-1});
i = j;
} else if (t.charAt(i) == '0' && t.charAt(i-1) == '1') {
int j = i;
while (j < n && t.charAt(j) == '0') j++;
if (t.charAt(j) == '1') zeros.add(new int[]{i, j-1});
i = j;
} else {
i++;
}
}
int ans = 0;
for (char c : s.toCharArray()) if (c == '1') ans++;
for (int[] o : ones) {
for (int[] z : zeros) {
char[] tmp = t.toCharArray();
for (int k = o[0]; k <= o[1]; k++) tmp[k] = '0';
for (int k = z[0]; k <= z[1]; k++) tmp[k] = '1';
int cnt = 0;
for (int k = 1; k < n-1; k++) if (tmp[k] == '1') cnt++;
ans = Math.max(ans, cnt);
}
}
return ans;
}
}
Kotlin
class Solution {
fun maximizeActiveSections(s: String): Int {
val t = "1" + s + "1"
val n = t.length
val ones = mutableListOf<Pair<Int, Int>>()
val zeros = mutableListOf<Pair<Int, Int>>()
var i = 0
while (i < n) {
if (t[i] == '1' && t[i-1] == '0') {
var j = i
while (j < n && t[j] == '1') j++
if (t[j] == '0') ones.add(i to j-1)
i = j
} else if (t[i] == '0' && t[i-1] == '1') {
var j = i
while (j < n && t[j] == '0') j++
if (t[j] == '1') zeros.add(i to j-1)
i = j
} else {
i++
}
}
var ans = s.count { it == '1' }
for (o in ones) {
for (z in zeros) {
val tmp = t.toCharArray()
for (k in o.first..o.second) tmp[k] = '0'
for (k in z.first..z.second) tmp[k] = '1'
val cnt = (1 until n-1).count { tmp[it] == '1' }
ans = maxOf(ans, cnt)
}
}
return ans
}
}
Python
class Solution:
def maximizeActiveSections(self, s: str) -> int:
t = '1' + s + '1'
n = len(t)
ones, zeros = [], []
i = 0
while i < n:
if t[i] == '1' and t[i-1] == '0':
j = i
while j < n and t[j] == '1':
j += 1
if t[j] == '0':
ones.append((i, j-1))
i = j
elif t[i] == '0' and t[i-1] == '1':
j = i
while j < n and t[j] == '0':
j += 1
if t[j] == '1':
zeros.append((i, j-1))
i = j
else:
i += 1
ans = s.count('1')
for o in ones:
for z in zeros:
tmp = list(t)
for k in range(o[0], o[1]+1):
tmp[k] = '0'
for k in range(z[0], z[1]+1):
tmp[k] = '1'
cnt = sum(1 for k in range(1, n-1) if tmp[k] == '1')
ans = max(ans, cnt)
return ans
Rust
impl Solution {
pub fn maximize_active_sections(s: String) -> i32 {
let t = format!("1{}1", s);
let n = t.len();
let t = t.chars().collect::<Vec<_>>();
let mut ones = vec![];
let mut zeros = vec![];
let mut i = 0;
while i < n {
if t[i] == '1' && t[i-1] == '0' {
let mut j = i;
while j < n && t[j] == '1' { j += 1; }
if t[j] == '0' { ones.push((i, j-1)); }
i = j;
} else if t[i] == '0' && t[i-1] == '1' {
let mut j = i;
while j < n && t[j] == '0' { j += 1; }
if t[j] == '1' { zeros.push((i, j-1)); }
i = j;
} else {
i += 1;
}
}
let mut ans = s.chars().filter(|&c| c == '1').count() as i32;
for &(o1, o2) in &ones {
for &(z1, z2) in &zeros {
let mut tmp = t.clone();
for k in o1..=o2 { tmp[k] = '0'; }
for k in z1..=z2 { tmp[k] = '1'; }
let cnt = (1..n-1).filter(|&k| tmp[k] == '1').count() as i32;
ans = ans.max(cnt);
}
}
ans
}
}
TypeScript
class Solution {
maximizeActiveSections(s: string): number {
const t = '1' + s + '1';
const n = t.length;
const ones: [number, number][] = [], zeros: [number, number][] = [];
let i = 0;
while (i < n) {
if (t[i] === '1' && t[i-1] === '0') {
let j = i;
while (j < n && t[j] === '1') j++;
if (t[j] === '0') ones.push([i, j-1]);
i = j;
} else if (t[i] === '0' && t[i-1] === '1') {
let j = i;
while (j < n && t[j] === '0') j++;
if (t[j] === '1') zeros.push([i, j-1]);
i = j;
} else {
i++;
}
}
let ans = 0;
for (const c of s) if (c === '1') ans++;
for (const o of ones) {
for (const z of zeros) {
const tmp = t.split('');
for (let k = o[0]; k <= o[1]; k++) tmp[k] = '0';
for (let k = z[0]; k <= z[1]; k++) tmp[k] = '1';
let cnt = 0;
for (let k = 1; k < n-1; k++) if (tmp[k] === '1') cnt++;
if (cnt > ans) ans = cnt;
}
}
return ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2), wherenis the length of the string, as we may try all pairs of blocks. - 🧺 Space complexity:
O(n), for storing the augmented string and temporary arrays.