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

Target Sum

Core idea: You're given an array of non-negative integers and a target. Put a + or a - in front of every number, add them up, and count the sign assignments whose total equals target. Brute force tries all 2^n sign patterns, but there is a clean reduction. Let P be the sum of the numbers that get + and N the sum of those that get -. Then P - N = target and P + N = total, so P = (total + target) / 2. The question becomes: how many subsets of nums sum to P? That is a standard 0/1 subset-sum counting knapsack: dp[s] is the number of subsets summing to s, updated per number with dp[s] += dp[s - num], iterating s descending so each number is used at most once. Guard first: if total + target is odd or |target| > total, the answer is 0. O(n·sum) time.


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.