Quick Overview

This question evaluates combinatorial counting, string manipulation, and optimization under constraints, along with handling large-number results via modular arithmetic.

Maximize weighted subsequence pairs with wildcards

Company: Amazon

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Online Assessment

You are given a string `s` of length `n` consisting only of characters `'0'`, `'1'`, and `'!'`. Each `'!'` can be replaced by either `'0'` or `'1'`. For the final binary string, define: - `count10` = number of index pairs `(i, j)` with `i < j`, `s[i] = '1'`, `s[j] = '0'` (a subsequence pair, not necessarily adjacent). - `count01` = number of index pairs `(i, j)` with `i < j`, `s[i] = '0'`, `s[j] = '1'`. Given integers `x` and `y`, the total “error” is: `error = x * count10 + y * count01`. Return the maximum possible `error` over all replacements of `'!'`, modulo `1_000_000_007`. Example: `s = "101!1"` (with given `x, y`).

Overview: This question evaluates combinatorial counting, string manipulation, and optimization under constraints, along with handling large-number results via modular arithmetic.

Part 1: Maximize weighted subsequence pair errors with wildcards

You are given a string s containing only '0', '1', and '!'. Each '!' must be replaced by either '0' or '1'. After all replacements, consider every pair of indices (i, j) with i < j: - if the characters form 01, that pair contributes x errors - if the characters form 10, that pair contributes y errors These are subsequence pairs, not substrings, so the two characters do not need to be adjacent. Return the maximum total number of errors possible after replacing all '!'. Because the answer can be large, return it modulo 10^9 + 7.

Constraints

  • 1 <= len(s) <= 2000
  • s contains only '0', '1', and '!'
  • 1 <= x, y <= 10^9

Examples

Input: ("101!1", 3, 2)

Expected Output:

Input: ("!", 5, 7)

Expected Output:

Hints

  1. Process the string from left to right. When you place the current bit, its contribution depends only on how many 0s and 1s already exist before it.
  2. For a prefix, you do not need the exact assignments of previous wildcards. It is enough to know how many of them were turned into 1s and the best score for that count.

Part 2: Maximize protected population by moving security units left once

There are n cities in a line, indexed from 1 to n. - population[i] is the population of city i + 1 in 0-based Python indexing. - unit is a binary string of length n. - unit[i] == '1' means city i + 1 initially has one security unit. Each security unit may either: - stay in its current city, or - move exactly one city to the left A unit can be moved at most once, and a unit in the first city cannot move left. After all moves, a city is considered protected if it has at least one unit. If multiple units end in the same city, that city still counts only once. Return the maximum total population of protected cities.

Constraints

  • 1 <= n == len(population) == len(unit) <= 2 * 10^5
  • 0 <= population[i] <= 10^9
  • unit contains only '0' and '1'

Examples

Input: ([10, 5, 8, 9, 6], "01101")

Expected Output:

Input: ([4, 7, 2], "000")

Expected Output:

Hints

  1. Consider each maximal consecutive block of 1s separately. Units from different blocks never need to interact.
  2. If a block of k consecutive units starts at position l > 1 and ends at r, those k units can protect any k cities inside the interval [l-1, r].

Loading coding console...

Show the approach

Approach

Key insight. Each '1' unit at city j can end up at city j or j-1. A run of k consecutive units occupying cities start..end can therefore reach exactly the k+1 cities {start-1, start, ..., end}. With k units and k+1 reachable cities, any k of those cities can be protected simultaneously (each unit picks a distinct target — a clean perfect-matching argument). So the best a block can do is grab the whole (k+1)-city window and sacrifice its single smallest population. Distinct blocks are separated by at least one '0', so their reachable windows never overlap and can be optimized independently.

Algorithm. Scan left to right, skipping '0's. When a '1' is found, consume the maximal run of '1's:

  • Block starts at index 0 — the city to the left (start-1) doesn't exist, so the units can only cover cities inside the block. Add the full block sum.
  • Block starts at index > 0 — the reachable window is population[start-1 .. end]. Accumulate block_sum over that whole window and track block_min, then add block_sum - block_min (drop the smallest).

The pointer i only ever moves forward, so every index is touched once.

Why correct. Dropping exactly the minimum is optimal because we are forced to leave out exactly one of the k+1 reachable cities, and leaving out the least populous one maximizes the kept total. The start==0 special case correctly forbids moving the first unit off the board.

Time complexity:
O(n)
Space complexity:
O(1)