3499. Maximize Active Section with Trade I

中文文档

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

The problem is essentially equivalent to finding the number of '1' characters in the string $\textit{s}$, plus the maximum number of '0' characters in two adjacent consecutive '0' segments.

Thus, we can use two pointers to traverse the string $\textit{s}$. Use a variable $\textit{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 $\textit{mx}$ as $\textit{mx} = \max(\textit{mx}, \textit{pre} + \textit{cnt})$, and update $\textit{pre}$ to $\textit{cnt}$. Finally, add $\textit{mx}$ to the answer.

Time complexity is $O(n)$, where $n$ is the length of the string $\textit{s}$. Space complexity is $O(1)$.

Python3

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

Java

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

C++

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

Go

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
}

TypeScript

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