</> MAANG.io

Advanced

Advanced problems where modelling is the hard part: implicit graphs, tricky DP states, intervals and design challenges.

0 of 95 solved 0%

Counting and Bitmask DP

What is this?

Two of these problems have a transition that sums a whole range of earlier states. That is correct, and too slow. Both collapse to a sliding window by writing the recurrence twice and subtracting. The other three are about state: a ± assignment problem that turns out to be subset sum, and two searches whose state is "what still needs covering" (a bitmask of covered target positions for Stickers, a start index for Word Break II) rather than a position in an input.

Counting and Bitmask: summed transition vs state of what's left (flowchart)

Fun fact: Target Sum asks how many ways to put + or − in front of each number to reach a target, and looks like 2ⁿ enumeration. Let P be the numbers you make positive and N the rest. Then P − N = target and P + N = total, so P = (total + target) / 2 and that is a fixed number. The question collapses to "how many subsets sum to P", an ordinary 0/1 knapsack count. As a bonus, two cheap checks answer 0 at once: total + target odd (parity), or |target| > total (out of range). Turning a signed-assignment problem into a subset sum by adding the two equations is a move worth keeping.

🔓 The 5 problems in this chapter are free. Sign in with Google or Microsoft to start solving.


Core idea: if a transition sums many earlier states, write it for k and for k−1 and subtract. Nearly every term cancels, and an entire dimension of work disappears.


1. Collapse the sum

The natural recurrence for K Inverse Pairs (inserting the n-th element can create 0 to n−1 new inversions) is a range sum:

dp[n][k] = dp[n-1][k] + dp[n-1][k-1] + … + dp[n-1][k-n+1]

Write the same line for k−1 and subtract. Everything cancels except the two edges:

dp[n][k] = dp[n][k-1] + dp[n-1][k] - dp[n-1][k-n]

O(n²k) becomes O(nk) time, and keeping only the previous row gives O(k) space. Two details bite: dp[n-1][k-n] only exists when k ≥ n, and the subtraction can go negative before the modulo, so normalise after every step.

2. The same move, as a window

New 21 Game draws uniformly from 1 … maxPts while below k, and asks for the probability of finishing at or below n (the problem guarantees k ≤ n). Each state is the mean of the previous maxPts states, the same summed transition, so the same fix:

dp[0], window, ans = 1.0, 1.0, 0.0
for i in range(1, n + 1):
    dp[i] = window / maxPts
    if i < k: window += dp[i]                      # still drawing
    else:     ans   += dp[i]                       # stopped here, and it counts
    if 0 <= i - maxPts < k: window -= dp[i-maxPts]  # slide the window

The guard is exact: a state leaves the window only if it was ever in it, which requires i - maxPts < k. The early exit if k == 0 or n >= k + maxPts - 1: return 1.0 handles the case where every possible final score is already at most n, so the answer is certain. Time is O(n); the dp array is O(n) space, and only the last maxPts values are ever read, so a ring buffer brings it to O(maxPts).

3. State that is "what remains"

Stickers to Spell Word uses a bitmask over the target's positions. dp[mask] is the fewest stickers still needed when the positions in mask are already covered:

@lru_cache(None)
def dp(mask):
    if mask == FULL: return 0
    i = lowest_uncovered(mask)                     # this position must be covered by SOME sticker
    for cnt in sticker_counts:
        if cnt[target[i]] == 0: continue           # the pruning that makes it feasible
        ...                                        # apply the sticker greedily, recurse on the new mask

Requiring every candidate sticker to contain the letter at the lowest uncovered position prunes the branching and costs nothing in correctness: that position has to be covered by some sticker, and the stickers of a solution can be applied in any order. Each transition covers at least that position, so the mask always grows. With n = len(target) there are at most 2ⁿ masks and each tries every sticker over the target, so time is O(2ⁿ · stickers · n) and space is O(2ⁿ). The small limit on the target length is what makes 2ⁿ states acceptable. If a needed letter appears in no sticker the answer is -1.

Word Break II is the same idea over suffixes. solve(start) returns the list of sentences that segment s[start:], memoised on the start index, rather than a count. Memoising stops the same suffix from being re-expanded for every prefix that reaches it, and a Word Break I reachability pass stops it from entering suffixes that cannot be segmented. The scans cost O(n³) in total, and building the sentences costs time proportional to their total size. That size can be exponential: for "aaaa…" with every run of as in the dictionary there are 2ⁿ⁻¹ sentences. That is a property of the question, not of the method.


4. A 30-second worked example (Target Sum)

nums = [1,1,1,1,1], target = 3

Target Sum worked example: answer 5

Two checks save the most time, and they fail for different reasons. With target = 2, total + target = 7 is odd, so P is not an integer and the answer is 0 (parity). With target = 7, total + target = 12 is even and P = 6, yet |target| > total means no assignment can reach it, so the answer is 0 (out of range). Either way the answer is 0 before a table is allocated.


5. Where you'll actually meet this

  • Probability under a stopping rule. New 21 Game is a bounded random walk that halts at a threshold, a small Markov chain.
  • Covering an order from packs. Stickers has the shape of "cover this requirement from these bundles using as few as possible", though real packing problems are rarely this small.
  • Text segmentation. Word Break II lists every way to split a string into dictionary words, the same task as segmenting text written without spaces.
  • Ranking comparison. Inversion counts measure how far one ordering is from another.
  • Exact-sum counting. Counting subsets that hit a fixed total is the same table as Target Sum.

6. Problems in this chapter

K Inverse Pairs Array

Count arrays with exactly k inverse pairs. The summed transition collapses to three terms by differencing adjacent states.
Pattern: counting DP with a collapsed range sum. Target: O(nk) time, O(k) space with two rolling rows.

New 21 Game

Probability of stopping at or below n. Each state is the mean of a fixed window of earlier states, maintained as a running sum.
Pattern: probability DP with a sliding window. Target: O(n) time, O(n) space (O(maxPts) with a ring buffer).

Target Sum

Count ± assignments reaching a target. Solve for the positive subset's sum and count subsets that reach it.
Pattern: subset-sum counting. Target: O(n · sum) time, O(sum) space.

Stickers to Spell Word

Fewest stickers spelling a target. Keep a bitmask of covered target positions and only try stickers containing the lowest uncovered letter.
Pattern: bitmask DP with memo. Target: O(2ⁿ · stickers · n) time, O(2ⁿ) space, n = len(target).

Word Break II

Every sentence formable from the dictionary. Memoise on the start index and return the list of completions of each suffix.
Pattern: memoised backtracking over suffixes. Target: O(n³) scans plus output-bound sentence building, and the output can reach 2ⁿ⁻¹.


7. Common pitfalls

  • Leaving the summed transition in place. It passes the samples and times out on the real constraints.
  • Reading dp[n-1][k-n] when k < n. That term does not exist and must be guarded.
  • Taking a modulo of a negative. Normalise after every subtraction.
  • Sliding the probability window unconditionally. A state only leaves if it ever entered, which needs i - maxPts < k.
  • Skipping the Target Sum feasibility checks. Parity (total + target odd) and range (|target| > total) are different failures, and both mean 0 immediately.
  • Reading Stickers' dp[mask] backwards. It is the number of stickers still needed from that state, with dp[FULL] = 0.
  • Dropping the lowest-uncovered-letter pruning, which is the difference between fast and hopeless.
  • Calling Word Break II polynomial. The scans are O(n³), but the sentences you build can be exponentially many.

8. Key takeaways

  1. A summed transition is a signal, not a solution. Difference adjacent states and it collapses.
  2. A sliding window is the same trick wearing a probability hat.
  3. Add the two equations. P − N = target with P + N = total turns signs into a subset sum.
  4. State can be "what is left" rather than "how far you have come".
  5. Pick a compact memo key. A bitmask of covered positions (Stickers) or a start index (Word Break II) lets equivalent states share one entry.
  6. A forced-coverage pruning is free correctness: the lowest uncovered position must be covered by some sticker, so only try stickers that can.
  7. Why interviewers like it: the naive recurrence is easy and quadratic, so the optimisation is precisely the thing being measured.

Order: K Inverse Pairs Array → New 21 Game → Target Sum → Stickers to Spell Word → Word Break II.

New 21 Game

Core idea: Alice draws a uniform integer from 1..maxPts, adds it to her score, and stops the instant her score reaches k. You want the probability that her final score is at most n. Let dp[x] be the probability of ever standing on score x. You can only land on x from a score in [x - maxPts, x - 1] that was still below k, and each such draw has probability 1/maxPts. So dp[x] is the sum of those dp values divided by maxPts. That sum is a sliding window of width maxPts: add the newest term, drop the one that fell off the back, and each state costs O(1). The answer is the probability mass that landed in k <= x <= n. O(n) time, O(n) space.


Sign in to continue reading

The rest of this lesson is available with a free account. Signing in with Google or Microsoft is free.

Sign in to read the full lesson

Sign in to MAANG.io

Use your Google or Microsoft account — no password to remember.

Continue with Google Continue with Microsoft

Please accept the terms above to continue.