Maximize Active Section with Trade I - Practice Coding Problems

Maximize Active Section with Trade I - Problem

String Enumeration Medium

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.

Input & Output

Example 1 — Basic Trade

$ Input: s = "10110"

› Output: 3

💡 Note: Original has 3 ones. No beneficial trade exists: trading any 1-block for 0-block results in net loss or no gain.

Example 2 — Beneficial Trade

$ Input: s = "1001"

› Output: 3

💡 Note: Original has 2 ones. Trade the middle 00 block for one of the 1 blocks: lose 1 one, gain 2 ones, net +1. Result: 2 + 1 = 3.

Example 3 — All Zeros

$ Input: s = "0000"

› Output: 0

💡 Note: No 1-blocks to trade away, so no trade is possible. Result remains 0.

Constraints

1 ≤ s.length ≤ 10⁵
s[i] is either '0' or '1'

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with 1s (active) and 0s (inactive)

Find Trades

Identify blocks of 1s and 0s for trading

Optimize

Choose trade that maximizes active sections

Key Takeaway

🎯 Key Insight: The optimal trade maximizes net gain (zeros gained minus ones lost)

Asked in

G Google 15 M Microsoft 12

The key insight is to find blocks of contiguous 1s and 0s, then calculate the net gain for each possible trade. The optimal approach uses direct calculation instead of string simulation. Time: O(b²) where b is number of blocks, Space: O(b)

Common Approaches

Approach	Time	Space	Notes
✓ Optimized Enumeration	O(b²)	O(b)	Pre-compute block information and calculate net gains efficiently
Brute Force - Try All Trades	O(n³)	O(n)	Enumerate all possible trades and find the one with maximum active sections

Optimized Enumeration — Algorithm Steps

Step 1: Parse string once to identify all contiguous blocks with positions and sizes
Step 2: For each valid trade pair, calculate net gain directly from block sizes
Step 3: Return original count plus maximum net gain

Visualization

Tap to expand

Step-by-Step Walkthrough

Parse Blocks

Extract block information with sizes in one pass

Calculate Gains

For each trade pair, compute net gain = zeros_gained - ones_lost

Best Trade

Return original count + maximum net gain

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char ch;
    int start, end, size;
} Block;

int solution(char* s) {
    int n = strlen(s);
    if (n == 0) return 0;
    
    // Augment string with '1' at both ends
    char* augmented = malloc(n + 3);
    sprintf(augmented, "1%s1", s);
    int augLen = n + 2;
    
    // Parse blocks efficiently
    Block blocks[1000];
    int blockCount = 0;
    
    int i = 0;
    while (i < augLen) {
        char ch = augmented[i];
        int start = i;
        while (i < augLen && augmented[i] == ch) {
            i++;
        }
        blocks[blockCount++] = (Block){ch, start, i - 1, i - start};
    }
    
    // Count initial 1s
    int initialCount = 0;
    for (int j = 0; j < n; j++) {
        if (s[j] == '1') initialCount++;
    }
    int maxGain = 0;
    
    // Calculate maximum net gain
    for (int a = 0; a < blockCount; a++) {
        if (blocks[a].ch != '1' || blocks[a].start == 0 || blocks[a].end == augLen - 1) continue;
        
        for (int b = 0; b < blockCount; b++) {
            if (blocks[b].ch != '0') continue;
            
            // Skip overlapping blocks
            if (!(blocks[a].end < blocks[b].start || blocks[b].end < blocks[a].start)) {
                continue;
            }
            
            // Calculate net gain (consider augmented boundaries)
            int zerosGained = blocks[b].size;
            if (blocks[b].start == 0) zerosGained--;
            if (blocks[b].end == augLen - 1) zerosGained--;
            
            int netGain = zerosGained - blocks[a].size;
            if (netGain > maxGain) {
                maxGain = netGain;
            }
        }
    }
    
    free(augmented);
    return initialCount + maxGain;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(b²)

b is number of blocks (typically O(n)), so O(n²) in worst case but much better constants

✓ Linear Growth

Space Complexity

O(b)

Storage for block information, typically O(n) space

✓ Linear Space

3.4K Views

Medium Frequency

~25 min Avg. Time

89 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Optimized Enumeration — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler