Welcome to Subscribe On Youtube

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)$.

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

All Problems

All Solutions