Skip to content

3499. Maximize Active Section with Trade I

SourceBiweekly Contest 153 Q2DifficultyMediumRating1729

Description

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'

Solutions

Solution 1: Greedy + Two Pointers

Thinking

One trade flips the \(0\)-runs on both sides of a \(1\)-run to \(1\). The gain is the sum of those two \(0\)-runs, plus every original \(1\). \(n\le 10^5\), so we scan runs.

Non-adjacent \(0\)-runs cannot be merged by a single trade, so only neighboring \(0\)-pairs matter.

Two pointers cut runs: \(1\)-runs add to the base answer; neighboring \(0\)-runs update \(mx\) by \(\textit{pre}+\textit{cur}\). The answer is the number of \(1\)s plus \(mx\).

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 \(\textit{pre}\) to record the number of '0' characters in the previous consecutive '0' segment.

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

The time complexity is \(O(n)\), and the space complexity is \(O(1)\), where \(n\) is the length of the string \(s\).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
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 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
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;
    }
}

 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
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
func maxActiveSectionsAfterTrade(s string) (ans int) {
    n := len(s)
    pre, mx := math.MinInt, 0

    for i := 0; i < n; {
        j := i + 1
        for j < n && s[j] == s[i] {
            j++
        }
        cur := j - i
        if s[i] == '1' {
            ans += cur
        } else {
            mx = max(mx, pre+cur)
            pre = cur
        }
        i = j
    }

    ans += mx
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function maxActiveSectionsAfterTrade(s: string): number {
    let n = s.length;
    let [ans, mx] = [0, 0];
    let pre = Number.MIN_SAFE_INTEGER;

    for (let i = 0; i < n;) {
        let j = i + 1;
        while (j < n && s[j] === s[i]) {
            j++;
        }
        let cur = j - i;
        if (s[i] === '1') {
            ans += cur;
        } else {
            mx = Math.max(mx, pre + cur);
            pre = cur;
        }
        i = j;
    }

    ans += mx;
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
impl Solution {
    pub fn max_active_sections_after_trade(s: String) -> i32 {
        let (ones_count, _, max_gain) = s.as_bytes().chunk_by(|left, right| left == right).fold(
            (0, i32::MIN, 0),
            |(ones_count, previous_zeros, max_gain), block| {
                let block_length = block.len() as i32;
                if block[0] == b'1' {
                    (ones_count + block_length, previous_zeros, max_gain)
                } else {
                    (
                        ones_count,
                        block_length,
                        max_gain.max(previous_zeros + block_length),
                    )
                }
            },
        );
        ones_count + max_gain
    }
}

Comments