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.

Example 1

1
2
3
4
5

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

1
2
3
4
5
6

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

1
2
3
4
5
6

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

1
2
3
4
5
6

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^5
  • s[i] is either '0' or '1'

Examples

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

  1. Augment the string: t = '1' + s + '1'.
  2. Find all blocks of ‘1’s surrounded by ‘0’s and all blocks of ‘0’s surrounded by ‘1’s in t.
  3. 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.
  4. If no valid trade, return the count of ‘1’s in s.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

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
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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), where n is 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.