3501. Maximize Active Section with Trade II

Description

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.

Additionally, you are given a 2D array queries, where queries[i] = [li, ri] represents a s[li...ri].

For each query, determine the maximum possible number of active sections in s after making the optimal trade on the substring s[li...ri].

Return an array answer, where answer[i] is the result for queries[i].

Note

• For each query, treat s[li...ri] as if it is augmented with a '1' at both ends, forming t = '1' + s[li...ri] + '1'. The augmented '1's do not contribute to the final count.
• The queries are independent of each other.

 

Example 1:

Input: s = "01", queries = [[0,1]]

Output: [1]

Explanation:

Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.

Example 2:

Input: s = "0100", queries = [[0,3],[0,2],[1,3],[2,3]]

Output: [4,3,1,1]

Explanation:

• Query [0, 3] → Substring "0100" → Augmented to "101001"
  Choose "0100", convert "0100" → "0000" → "1111".
  The final string without augmentation is "1111". The maximum number of active sections is 4.

• Query [0, 2] → Substring "010" → Augmented to "10101"
  Choose "010", convert "010" → "000" → "111".
  The final string without augmentation is "1110". The maximum number of active sections is 3.

• Query [1, 3] → Substring "100" → Augmented to "11001"
  Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.

• Query [2, 3] → Substring "00" → Augmented to "1001"
  Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 1.

Example 3:

Input: s = "1000100", queries = [[1,5],[0,6],[0,4]]

Output: [6,7,2]

Explanation:

• Query [1, 5] → Substring "00010" → Augmented to "1000101"
  Choose "00010", convert "00010" → "00000" → "11111".
  The final string without augmentation is "1111110". The maximum number of active sections is 6.

• Query [0, 6] → Substring "1000100" → Augmented to "110001001"
  Choose "000100", convert "000100" → "000000" → "111111".
  The final string without augmentation is "1111111". The maximum number of active sections is 7.

• Query [0, 4] → Substring "10001" → Augmented to "1100011"
  Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 2.

Example 4:

Input: s = "01010", queries = [[0,3],[1,4],[1,3]]

Output: [4,4,2]

Explanation:

• Query [0, 3] → Substring "0101" → Augmented to "101011"
  Choose "010", convert "010" → "000" → "111".
  The final string without augmentation is "11110". The maximum number of active sections is 4.

• Query [1, 4] → Substring "1010" → Augmented to "110101"
  Choose "010", convert "010" → "000" → "111".
  The final string without augmentation is "01111". The maximum number of active sections is 4.

• Query [1, 3] → Substring "101" → Augmented to "11011"
  Because there is no block of '1's surrounded by '0's, no valid trade is possible. The maximum number of active sections is 2.

 

Constraints:

• 1 <= n == s.length <= 105
• 1 <= queries.length <= 105
• s[i] is either '0' or '1'.
• queries[i] = [li, ri]
• 0 <= li <= ri < n

 

Solutions

Solution: Sparse Table

• Time complexity: O(nlogn)
• Space complexity: O(nlogn)

 

JavaScript

/**
 * @param {string} s
 * @param {number[][]} queries
 * @return {number[]}
 */
const maxActiveSectionsAfterTrade = function (s, queries) {
  const n = s.length;
  const { zeroGroups, zeroGroupIndex } = createZeroGroups(s);
  let ones = 0;

  for (let index = 0; index < n; index++) {
    const value = Number(s[index]);

    ones += value;
  }

  if (zeroGroups.length < 2) {
    return queries.map(() => ones);
  }

  const mergeZeroGroups = [];

  for (let index = 1; index < zeroGroups.length; index++) {
    const a = zeroGroups[index - 1].length;
    const b = zeroGroups[index].length;

    mergeZeroGroups.push(a + b);
  }

  const st = new SparseTable(mergeZeroGroups);

  return queries.map(([l, r]) => {
    const lIndex = zeroGroupIndex[l];
    const lGroup = zeroGroups[lIndex];
    const left = lIndex === -1 ? -1 : lGroup.length - l + lGroup.start;
    const rIndex = zeroGroupIndex[r];
    const rGroup = zeroGroups[rIndex];
    const right = rIndex === -1 ? -1 : r - rGroup.start + 1;
    const startGroupIndex = lIndex + 1;
    const endGroupIndex = s[r] === '0' ? rIndex - 1 : rIndex;
    let maxOnes = ones;

    if (s[l] === '0' && s[r] === '0' && startGroupIndex === rIndex) {
      maxOnes = Math.max(left + right + ones, maxOnes);
    } else if (startGroupIndex <= endGroupIndex - 1) {
      const maxMerge = st.query(startGroupIndex, endGroupIndex - 1);

      maxOnes = Math.max(maxMerge + ones, maxOnes);
    }

    if (s[l] === '0' && startGroupIndex <= endGroupIndex) {
      const nextGroup = zeroGroups[startGroupIndex];

      maxOnes = Math.max(left + nextGroup.length + ones, maxOnes);
    }

    if (s[r] === '0' && startGroupIndex <= endGroupIndex) {
      const prevGroup = zeroGroups[endGroupIndex];

      maxOnes = Math.max(right + prevGroup.length + ones, maxOnes);
    }

    return maxOnes;
  });
};

class SparseTable {
  constructor(nums) {
    const n = nums.length;
    const maxK = 32 - Math.clz32(n);

    this.st = Array.from({ length: maxK + 1 }, () => new Array(n).fill(0));

    for (let index = 0; index < n; index++) {
      this.st[0][index] = nums[index];
    }

    for (let log = 1; log <= maxK; log++) {
      const half = 1 << (log - 1);

      for (let index = 0; index + half < n; index++) {
        const intervalA = this.st[log - 1][index];
        const intervalB = this.st[log - 1][index + half];

        this.st[log][index] = Math.max(intervalA, intervalB);
      }
    }
  }

  query(l, r) {
    const len = r - l + 1;
    const log = 31 - Math.clz32(len);
    const half = 1 << log;

    return Math.max(this.st[log][l], this.st[log][r - half + 1]);
  }
}

function createZeroGroups(s) {
  const n = s.length;
  const zeroGroups = [];
  const zeroGroupIndex = [];

  for (let index = 0; index < n; index++) {
    if (s[index] === '0') {
      if (s[index - 1] === '0') {
        zeroGroups.at(-1).length += 1;
      } else {
        zeroGroups.push({ start: index, length: 1 });
      }
    }

    zeroGroupIndex.push(zeroGroups.length - 1);
  }

  return { zeroGroups, zeroGroupIndex };
}