Maximize Active Section with Trade I

Medium
1778.

Maximize Active Section with Trade I

Maximize Active Section with Trade I is a medium coding problem on strings and enumeration, asked in Google interviews.

You are given a binary string s of length n, where '1' marks an active section and '0' an inactive one.

You may perform at most one trade. A trade is two steps, done in order:

  1. pick a contiguous block of '1's that is surrounded by '0's on both sides and turn all of it into '0's;
  2. then pick a contiguous block of '0's that is surrounded by '1's on both sides and turn all of it into '1's.

For the purpose of the trade only, treat s as if it had an extra '1' at each end (t = '1' + s + '1'); those two added characters are never counted.

Return the maximum number of '1's that s can contain after the best choice.

Example 1

Input
s = "01"
Output
1
Explanation
No block of '1's is surrounded by '0's, so no trade is possible.

Example 2

Input
s = "0100"
Output
4
Explanation
With t = "101001", zero the middle '1' to get "100001", then fill the zero block to get "111111": all 4 characters of s are '1'.

Example 3

Input
s = "1000100"
Output
7
Explanation
t = "110001001". Zero the lone '1' between the zero blocks ("110000001"), then fill them all: every character of s becomes '1'.

Constraints

  • 1 <= n == s.length <= 10^5
  • s[i] is either '0' or '1'
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {string} s
 * @return {number}
 */
var maxActiveSectionsAfterTrade = function(s) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximize Active Section with Trade I — Problem & Solution

Maximize Active Section with Trade I solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Maximize Active Section with Trade I is a medium coding problem on strings and enumeration, asked in Google interviews.

  • Difficulty: Medium
  • Topics: Strings, Enumeration
  • Asked at: Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

You are given a binary string s of length n, where '1' marks an active section and '0' an inactive one.

You may perform at most one trade. A trade is two steps, done in order:

  1. pick a contiguous block of '1's that is surrounded by '0's on both sides and turn all of it into '0's;
  2. then pick a contiguous block of '0's that is surrounded by '1's on both sides and turn all of it into '1's.

For the purpose of the trade only, treat s as if it had an extra '1' at each end (t = '1' + s + '1'); those two added characters are never counted.

Return the maximum number of '1's that s can contain after the best choice.

Example 1

Input: s = "01"
Output: 1
Explanation: No block of '1's is surrounded by '0's, so no trade is possible.

Example 2

Input: s = "0100"
Output: 4
Explanation: With t = "101001", zero the middle '1' to get "100001", then fill the zero block to get "111111": all 4 characters of s are '1'.

Example 3

Input: s = "1000100"
Output: 7
Explanation: t = "110001001". Zero the lone '1' between the zero blocks ("110000001"), then fill them all: every character of s becomes '1'.

Constraints

  • 1 <= n == s.length <= 10^5
  • s[i] is either '0' or '1'

Hints for Maximize Active Section with Trade I

  1. Hint 1

    Step 1 can only remove a block of '1's that has a block of '0's directly on each side — it merges those two zero blocks into one big block.

  2. Hint 2

    Step 2 should then fill that merged block: you lose the removed ones but gain them back, plus both zero blocks.

  3. Hint 3

    So the gain is the sum of two consecutive zero blocks. Take the best such pair and add it to the number of '1's already in s; with fewer than two zero blocks no trade helps.

How to solve Maximize Active Section with Trade I

Removing a '1' block that separates zero blocks of sizes z1 and z2 creates one zero block of size z1 + o + z2, and filling it gives back the o ones plus z1 + z2 new ones. So a trade gains the sum of two adjacent zero blocks; the answer is the count of ones plus the best adjacent pair.

Approach

  1. Count the '1's in s.
  2. Scan s for its maximal blocks of '0's, in order, remembering the length of the previous block.
  3. For each block after the first, update best = max(best, previous + current).
  4. Return ones + best (best stays 0 when there are fewer than two zero blocks).

Why it works

In the augmented string any '1' block surrounded by zeros lies between two consecutive zero blocks of s. After removing it, filling the merged block gains z1 + z2; filling any other zero block z gains z - o < z, and z itself is part of some adjacent pair whose sum is at least z. Hence the best trade gains exactly the largest adjacent-pair sum, and not trading gains 0.

Complexity

  • Time — O(n)
  • Space — O(1)

Pitfalls

  • A '1' block touching either end of s is next to the augmented '1', not a '0', so it cannot be removed.
  • The augmented '1's are never counted in the answer.
  • Two zero blocks are always separated by a '1' block, so consecutive zero blocks in a scan are exactly the pairs a trade can merge.

Reference solution

Python

def maxActiveSectionsAfterTrade(s: str) -> int:
    ones = s.count("1")
    best, prev = 0, -1
    n, i = len(s), 0
    while i < n:
        if s[i] == "1":
            i += 1
            continue
        j = i
        while j < n and s[j] == "0":
            j += 1
        cur = j - i
        if prev >= 0:
            best = max(best, prev + cur)
        prev = cur
        i = j
    return ones + best

Java

public static int maxActiveSectionsAfterTrade(String s) {
    int n = s.length(), ones = 0, best = 0, prev = -1, i = 0;
    for (int k = 0; k < n; k++) if (s.charAt(k) == '1') ones++;
    while (i < n) {
        if (s.charAt(i) == '1') { i++; continue; }
        int j = i;
        while (j < n && s.charAt(j) == '0') j++;
        int cur = j - i;
        if (prev >= 0) best = Math.max(best, prev + cur);
        prev = cur;
        i = j;
    }
    return ones + best;
}

C++

int maxActiveSectionsAfterTrade(string s) {
    int n = s.size(), ones = 0, best = 0, prev = -1, i = 0;
    for (char c : s) if (c == '1') ones++;
    while (i < n) {
        if (s[i] == '1') { i++; continue; }
        int j = i;
        while (j < n && s[j] == '0') j++;
        int cur = j - i;
        if (prev >= 0) best = max(best, prev + cur);
        prev = cur;
        i = j;
    }
    return ones + best;
}

JavaScript

var maxActiveSectionsAfterTrade = function(s) {
    var n = s.length, ones = 0, best = 0, prev = -1, i = 0;
    for (var k = 0; k < n; k++) if (s[k] === "1") ones++;
    while (i < n) {
        if (s[i] === "1") { i++; continue; }
        var j = i;
        while (j < n && s[j] === "0") j++;
        var cur = j - i;
        if (prev >= 0 && prev + cur > best) best = prev + cur;
        prev = cur;
        i = j;
    }
    return ones + best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 515 strings problems · the whole catalogue

Learn the technique: Strings