Problem Statement in English

You’re given a string s consisting of ‘0’s and ‘1’s.

1 represents an active section, and 0 represents an inactive section.

You can perform atmost one trade to maximise the number of active sections.

In one trade, you:

  • convert a contiguous block of inactive sections (0’s) into active sections (1’s) if it is surrounded by active sections (1’s) on both sides.
  • convert a contiguous block of active sections (1’s) into inactive sections (0’s) if it is surrounded by inactive sections (0’s) on both sides.

Return the maximum number of active sections you can have after performing at most one trade.

Note: Treat the string s as augmented with a ‘1’ at the start and end of the string. The augmented 1s do not count towards the number of active sections.

Approach

Fundamentally, we can think about the string in terms of blocks of contiguous characters.

Assume that we have a block of 0s of length $Z_1$, and it’s surrounded by blocks of 1s of lengths $O_1$ and $O_2$.

We parse the string into blocks of contiguous characters, and for each block of ‘1’s that is surrounded by ‘0’s, we can calculate the gain in active sections if we were to convert the surrounding 0s into 1s.

This tells us that the maximum gain we can get from a single trade is the sum of the lengths of the two surrounding 0 blocks.

Now that we’ve parsed the string into blocks, we can iterate through the blocks and for each block of ‘1’s, it’s guaranteed that is surrounded by ‘0’s, since we’ve already parsed the string, we can calculate the gain in active sections if we were to convert the surrounding 0s into 1s.

And we’re done!

Solution in Python


class Solution:
    def maxActiveSectionsAfterTrade(self, s: str) -> int:
        initial_ones = s.count('1')
        
        # Augment s
        t = '1' + s + '1'
        
        # Parse alternating blocks of characters and their lengths
        blocks = []
        i = 0
        n = len(t)
        while i < n:
            j = i
            while j < n and t[j] == t[i]:
                j += 1
            blocks.append((t[i], j - i))
            i = j
            
        max_gain = 0
        
        # Check every valid '1' block surrounded by '0' blocks
        # Non-augmented '1' blocks start from index 2 to len(blocks) - 3
        for k in range(2, len(blocks) - 2):
            char, length = blocks[k]
            if char == '1':
                # Since it's '1', its neighbors blocks[k-1] and blocks[k+1] must be '0's
                z_left = blocks[k - 1][1]
                z_right = blocks[k + 1][1]
                gain = z_left + z_right
                max_gain = max(max_gain, gain)
                
        return initial_ones + max_gain

Complexity

  • Time: $O(n)$
    Since we process $n$ characters at most.

  • Space: $O(n)$
    Since we store the blocks of contiguous characters in a list.

Mistakes I Made

Had to look this up :(

And we are done.