Independent Active-Section Trade Queries

Quick Overview

Answer independent binary-string trade queries while counting active sections across the whole string. Restrict both trade steps to each substring and preserve its virtual boundary rules.

Independent Active-Section Trade Queries

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: hard

Interview Round: Other

### Problem You are given a binary string `s`, where `1` marks an active section and `0` marks an inactive section, and inclusive, zero-based queries `[l, r]`. For each query independently, you may perform at most one trade entirely within `s[l...r]`. A trade has two ordered steps: 1. Change a contiguous block of `1`s immediately surrounded by `0`s into zeros. 2. In the resulting substring, change a contiguous block of `0`s immediately surrounded by `1`s into ones. For this query's surrounding-character checks, treat its substring as `"1" + s[l...r] + "1"`. The added ones are not original sections and are not counted. Return one answer per query: the maximum number of active sections in the **whole string `s`** after that query's allowed trade. Characters outside `[l,r]` remain unchanged. Queries do not accumulate changes; each starts with the original string. Performing no trade is allowed, but performing only the second step is not. ### C++ Interface ```cpp class Solution { public: vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) { } }; ``` ### Examples **Example 1** ```text Input: s = "0011000100", queries = [[0,9],[1,8],[2,7],[4,9]] Output: [8,7,3,8] ``` The original string has three ones. For `[0,9]`, changing the ones at indices `2,3` to zero and then changing indices `0...6` to one gives eight active sections. For `[1,8]`, the same first step followed by changing indices `1...6` to one gives seven. Query `[2,7]` permits no legal first step and leaves the global count at three. For `[4,9]`, trading the one at index `7` makes that entire six-character substring active; the two ones outside it bring the answer to eight. **Example 2** ```text Input: s = "110010001", queries = [[0,8],[3,6],[0,3],[5,5]] Output: [9,7,4,4] ``` The original global count is four. In `[0,8]`, trading the one at index `4` can make the whole string active. In `[3,6]`, the substring is `"0100"`; completing its trade makes its four positions active, while three original ones outside the query remain, giving seven. Neither `[0,3]` nor `[5,5]` allows a first step, so their answers remain four. ### Constraints - `1 <= n == s.length <= 100000`. - `1 <= queries.length <= 100000`. - Every `s[i]` is `0` or `1`. - Each query contains exactly two integers `[l, r]`. - `0 <= l <= r < n`. ### Clarifying Questions - Does an answer count only ones inside the queried substring? No. It counts the whole string after changing only that substring. - Do actual characters just outside the query determine whether its edge blocks are surrounded? No. Use the query's two added boundary ones. - Do earlier answers change the string for later queries? No. All queries are independent. - What happens if no trade is legal? Return the original string's active count for that query. ### What a Strong Answer Covers - Both ordered trade steps, their legality inside the queried substring, and the option of no trade. - Query-specific surrounding characters and their exclusion from the count. - The whole-string answer and independence of different queries. - Single-position queries, queries reaching string edges, and the maximum string and query counts. - An optimality argument and suitable time, space, and numeric bounds. ### Follow-up Questions - Can a query containing only zeros still have a positive answer under this whole-string counting rule? - Which part of the specification would change if query effects were cumulative instead of independent? ```hint Reuse the unchanged string Describe the string by its maximal zero and one runs. A trade that removes an internal one-run can gain the lengths of its two neighboring zero-runs. Precompute range maxima for fully included neighboring pairs, and handle zero-runs clipped by a query boundary separately. ```

Overview: Answer independent binary-string trade queries while counting active sections across the whole string. Restrict both trade steps to each substring and preserve its virtual boundary rules.

Google logo
Google
hardSoftware EngineerOtherCoding & Algorithms
1
0

Problem

You are given a binary string s, where 1 marks an active section and 0 marks an inactive section, and inclusive, zero-based queries [l, r].

For each query independently, you may perform at most one trade entirely within s[l...r]. A trade has two ordered steps:

  1. Change a contiguous block of 1 s immediately surrounded by 0 s into zeros.
  2. In the resulting substring, change a contiguous block of 0 s immediately surrounded by 1 s into ones.

For this query's surrounding-character checks, treat its substring as "1" + s[l...r] + "1". The added ones are not original sections and are not counted.

Return one answer per query: the maximum number of active sections in the whole string s after that query's allowed trade. Characters outside [l,r] remain unchanged. Queries do not accumulate changes; each starts with the original string. Performing no trade is allowed, but performing only the second step is not.

C++ Interface

class Solution {
public:
    vector<int> maxActiveSectionsAfterTrade(string s, vector<vector<int>>& queries) {
        
    }
};

Examples

Example 1

Input: s = "0011000100", queries = [[0,9],[1,8],[2,7],[4,9]]
Output: [8,7,3,8]

The original string has three ones. For [0,9], changing the ones at indices 2,3 to zero and then changing indices 0...6 to one gives eight active sections. For [1,8], the same first step followed by changing indices 1...6 to one gives seven. Query [2,7] permits no legal first step and leaves the global count at three. For [4,9], trading the one at index 7 makes that entire six-character substring active; the two ones outside it bring the answer to eight.

Example 2

Input: s = "110010001", queries = [[0,8],[3,6],[0,3],[5,5]]
Output: [9,7,4,4]

The original global count is four. In [0,8], trading the one at index 4 can make the whole string active. In [3,6], the substring is "0100"; completing its trade makes its four positions active, while three original ones outside the query remain, giving seven. Neither [0,3] nor [5,5] allows a first step, so their answers remain four.

Constraints

  • 1 <= n == s.length <= 100000 .
  • 1 <= queries.length <= 100000 .
  • Every s[i] is 0 or 1 .
  • Each query contains exactly two integers [l, r] .
  • 0 <= l <= r < n .

Clarifying Questions Guidance

  • Does an answer count only ones inside the queried substring? No. It counts the whole string after changing only that substring.
  • Do actual characters just outside the query determine whether its edge blocks are surrounded? No. Use the query's two added boundary ones.
  • Do earlier answers change the string for later queries? No. All queries are independent.
  • What happens if no trade is legal? Return the original string's active count for that query.

What a Strong Answer Covers Guidance

  • Both ordered trade steps, their legality inside the queried substring, and the option of no trade.
  • Query-specific surrounding characters and their exclusion from the count.
  • The whole-string answer and independence of different queries.
  • Single-position queries, queries reaching string edges, and the maximum string and query counts.
  • An optimality argument and suitable time, space, and numeric bounds.

Follow-up Questions Guidance

  • Can a query containing only zeros still have a positive answer under this whole-string counting rule?
  • Which part of the specification would change if query effects were cumulative instead of independent?