Maximize weighted subsequence pairs with wildcards
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Take-home Project
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`).
Quick Answer: 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
- 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.
- 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
- Consider each maximal consecutive block of 1s separately. Units from different blocks never need to interact.
- 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].