We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Maximize Active Section with Trade II

Number: 3804

Difficulty: Hard

Paid? No

Companies: N/A

Problem Description

We are given a binary string s of length n where a character '1' represents an active section and '0' an inactive section. You may perform at most one “trade” on a chosen substring s[l…r]. For the trade the substring is first “augmented” by prepending and appending a virtual '1' (these extra ones do not count in the final answer). Then the allowed operation is to pick a contiguous block inside the augmented substring that satisfies a “trade‐valid” pattern – namely, it must start and end with a 0 (these 0’s come from the original substring) and the block must contain at least one 1. In the two‐step process the block’s ones are first “removed” (set to 0) and then the resulting full block (which is now entirely 0’s and is flanked by 1’s by augmentation) is converted into 1’s. In other words, by “trading” on an appropriately chosen subinterval U ⊆ s[l…r] (with U[0] = U[last] = '0' and U contains at least one '1') the net effect on U is that every character becomes active. (Of course, you may also decide to perform no trade.)

Since the trade is applied only to the substring while the rest of s remains unchanged, the overall final active–section count equals the ones outside plus the result inside. For a given query the “do nothing” answer equals the original count of ones in s[l…r] plus the ones outside (which is fixed). A successful trade on some candidate U will “improve” the section by replacing its original ones by an interval of all ones; the net gain on s[l…r] equals   (length(U) – (number of ones originally in U)).

Our goal is to choose (if possible) a valid subinterval U ⊆ s[l…r] on which to perform this two–step trade so as to maximize the final overall count of ones in s.

Note that if no valid candidate exists within the query interval then no trade can be performed and the answer remains the original active count in s.

For example, consider s = "0100":
 • Query [0,3]: The substring is "0100". Augmenting gives "1 0100 1". Notice that the entire interval “0100” is trade–valid (it starts and ends with '0' and contains a 1) so performing the trade converts it into "1111". Since s has no ones outside the substring the overall answer becomes 4.
 • Query [1,3]: The substring "100" (augmented to "1 100 1") has no valid candidate because the only one is at the beginning (and the block would not be “surrounded by” 0’s). Thus no trade is possible and the answer remains the original count (which is 1).
 • Query [2,3]: The substring "00" is all inactive; no candidate block exists so the answer remains 0 within the substring – and overall (when combined with the outside parts) the maximum active count becomes 1.

In several examples the optimal trade completely “flips” a candidate subinterval (which may or may not be the entire query interval) so that after adding the unchanged ones outside the substring the final count is higher.

Key Insights

  • The overall effect of a valid trade on a chosen subinterval U is to “gain” extra active sections equal to:   gain = (length(U) – (# ones originally in U)).
  • The conditions for a valid U (taken from within s[l…r]) are that its first and last characters must be '0' and it must contain at least one '1'.
  • Because the trade is applied only to s[l…r] (with the rest of s fixed), the overall answer equals:   (answer on substring) + (ones outside)
    and since the “do nothing” baseline is fixed, a trade is only beneficial when the gain is positive.
  • One can show that if any valid candidate exists in s[l…r], then the best candidate is obtained by choosing the interval that spans the leftmost and rightmost occurrences of '0' in s[l…r] (subject to the candidate containing at least one '1').
  • Precomputing the prefix–sum of ones allows us to compute the number of ones in any substring quickly.
  • Also, by building an array Z of all indices in s with a '0', one can answer “range” queries by binary–searching the first and last indices in Z that lie inside a given query interval.

Space and Time Complexity

Time Complexity: O(n + q · log n)
 • O(n) to build the prefix sums and the list Z.
 • O(log n) per query due to binary search in Z.
Space Complexity: O(n) for the prefix arrays and the list Z.

Solution

The idea is to view the trade as “flipping” a chosen subinterval U ⊆ s[l…r] (which must begin and end with '0' and contain at least one '1') so that U becomes all ones. For that candidate U the net “gain” in active ones inside the query interval is:   gain = (# zeros in U) = (length(U) – (# ones in U)). Then the best overall final active count (after trade) is the sum of active sections outside s[l…r] (which remain unchanged) plus the improved count inside s[l…r]:   final = (total ones in s – ones in s[l…r]) + max(ones in s[l…r], ones in s[l…r] + gain) If no valid candidate exists in s[l…r] (for example, if there are fewer than 2 zeros in that range or the candidate interval contains no one) then we cannot apply a trade and the answer is simply the original total ones in s. To answer many queries efficiently, we use:  1. A prefix–sum array (or equivalent) to count ones quickly in any interval.  2. An array Z which holds all indices i where s[i] == '0'. For each query [l,r] we binary–search Z to find the first and last index lying in [l,r]. If at least two such indices exist and the interval between them (from i to j) contains at least one '1' (i.e. (j – i + 1) > (# zeros in that interval)), then a valid trade candidate exists and the maximum gain equals the number of zeros in that candidate (which is j_index – i_index + 1).
Thus, overall answer for a query is:   if candidate exists: totalOnes + (number of zeros in candidate)
  else: totalOnes
This works because the ones outside the query are fixed and, for a trade candidate in the query, the best “flipping” turns the candidate completely active.

Code Solutions

Below are code solutions in Python, JavaScript, C++, and Java with detailed line–by–line comments.

# Python solution

import bisect

class Solution:
    def maximizeActiveSections(self, s: str, queries: list) -> list:
        n = len(s)
        # Precompute prefix-sum for ones in s: prefix1[i] = count of '1's in s[:i]
        prefix1 = [0] * (n+1)
        for i in range(n):
            prefix1[i+1] = prefix1[i] + (1 if s[i]=='1' else 0)
        
        totalOnes = prefix1[n]
        
        # Build list Z of indices where s[i]=='0'
        zerosPositions = [i for i, ch in enumerate(s) if ch=='0']
        
        res = []
        for l, r in queries:
            # Count ones in the query substring s[l:r+1]
            ones_sub = prefix1[r+1] - prefix1[l]
            
            # By default, if no trade, the substring remains as is.
            # The overall final count would be ones outside + ones_sub = totalOnes.
            bestSub = ones_sub
            
            # Use binary search in zerosPositions to get indices in [l, r]
            left_idx = bisect.bisect_left(zerosPositions, l)
            right_idx = bisect.bisect_right(zerosPositions, r) - 1
            
            # A candidate trade requires at least two zeros inside.
            if left_idx < len(zerosPositions) and right_idx < len(zerosPositions) and left_idx < right_idx:
                leftZero = zerosPositions[left_idx]
                rightZero = zerosPositions[right_idx]
                # Number of zeros from leftZero to rightZero can be computed
                # by the number of elements in zerosPositions between left_idx and right_idx.
                candidateZeros = (right_idx - left_idx + 1)
                # Length of interval from leftZero to rightZero
                intervalLength = rightZero - leftZero + 1
                # The number of ones in the candidate interval = intervalLength - candidateZeros.
                if intervalLength - candidateZeros >= 1:
                    # Valid candidate exists; improvement equals candidateZeros.
                    improvement = candidateZeros
                    # Trading will turn the entire candidate interval to ones.
                    bestSub = ones_sub + improvement
            
            # The overall result for s is ones outside (totalOnes - ones_sub) plus the traded substring result.
            res.append((totalOnes - ones_sub) + bestSub)
        return res

# Example usage:
# s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]
# sol = Solution()
# print(sol.maximizeActiveSections(s, queries))  # Expected: [4,3,1,1]
← Back to All Questions