How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Take-home Project rounds at Amazon.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Amazon during technical interviews.

Maximize weighted subsequence pairs with wildcards

Quick Overview

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

Loading coding console...

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:

Explanation: Move the unit from city 2 to city 1, keep city 3's unit in place, and move the unit from city 5 to city 4. Protected populations are 10 + 8 + 9 = 27.

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

Expected Output:

Explanation: There are no security units, so no city can be protected.

Input: ([6, 2, 9], "110")

Expected Output:

Explanation: The first unit cannot move left. The best result is to keep units in cities 1 and 2, protecting 6 + 2 = 8.

Input: ([3, 9, 4], "011")

Expected Output:

Explanation: The two adjacent units can protect any 2 of the 3 cities in positions 1..3. The best choice is populations 9 and 4.

Input: ([2, 8, 1, 7], "0101")

Expected Output:

Explanation: Use the unit at city 2 to protect city 2, and the unit at city 4 to protect city 4. Total is 8 + 7 = 15.

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].

Quick Overview