Spell a word with letter blocks, one block per letter

Question: Spell a word with letter blocks, one block per letter

Companies: Amazon

Difficulty: Medium

Problem statement

You have a set of letter blocks. Each block is a list of lowercase characters printed on its faces. You also get a target string.

Implement can_form(blocks: list[list[str]], target: str) -> bool. Return True if you can spell target by taking one character from a block for each position of target, where:

• each block is used for at most one position,
• the blocks can be used in any order, and
• a block that shows the same letter twice still counts as one block.

Constraints: 0 <= len(target) <= 1000, 0 <= len(blocks) <= 1000, each block has 1 to 26 characters.

Example 1

blocks = [["m", "q"], ["o", "p"], ["p", "m"]]
target = "mop"
-> True   # m from block 0, o from block 1, p from block 2

Example 2

blocks = [["r", "s"], ["r"], ["t"]]
target = "rrs"
-> False  # only two blocks have 'r', and one of them is also the only block with 's'

A natural follow-up: return which block is used for each position of target.

Reconstructed from the reported question; details may differ from what interviewers ask.

Approach

Restate it as a matching problem. Every position of target needs
its own block, and every block can serve at most one position. Build a
bipartite graph: target positions on the left, blocks on the right, and
an edge from position i to block b when b contains target[i]. The
target can be formed exactly when this graph has a matching that covers
every left node, i.e. a maximum matching of size len(target).

Quick rejections first. If len(target) > len(blocks) the answer is
False without any search. If some letter in target appears in no
block at all, the answer is also False.

Brute force. Try every way to give each position a distinct block
(backtracking). That is up to B! / (B - n)! assignments, exponential.
It is worth saying out loud, because many candidates then try a greedy
"take the first block that has the letter" and get it wrong:

• blocks ["ab", "a"], target "ab": greedy gives block 0 to 'a',
  then no block is left with 'b'. The right choice is block 1 for 'a'.

Greedy cannot know which block a later position will need. Matching
fixes this with augmenting paths.

Optimal: Kuhn's augmenting paths. Process positions one at a time.
For position i, DFS over blocks that contain target[i]:

• If a block is free, take it.
• If a block is held by position j, try to move j to another block
  (recursive DFS). If j can move, i takes the block.

A visited set per top-level search stops the DFS from revisiting a
block, so one search is O(edges). If any position fails to find an
augmenting path, the answer is False: Berge's theorem says a matching
with no augmenting path is maximum, so no reordering of earlier choices
could help.

Compress by letter (optimization worth mentioning). Positions with
the same letter are interchangeable. Group the target into letter counts
and run max flow source -> letter (cap = count) -> block (cap 1) -> sink. The left side then has at most 26 nodes, which matters when the
target is long and repetitive.

Invariants:

• owner[b] is the target position currently using block b, or -1.
• After position i is placed, positions 0..i are all matched and
  each holds a distinct block containing its letter.

Code

from __future__ import annotations

from collections import defaultdict


def can_form(blocks: list[list[str]], target: str) -> bool:
    return assign_blocks(blocks, target) is not None


def assign_blocks(blocks: list[list[str]], target: str) -> list[int] | None:
    """Return block index used for each target position, or None."""
    n, m = len(target), len(blocks)
    if n > m:
        return None

    # letter -> blocks that contain it (dedupe letters inside a block)
    blocks_with: dict[str, list[int]] = defaultdict(list)
    for b, chars in enumerate(blocks):
        for ch in set(chars):
            blocks_with[ch].append(b)

    if any(ch not in blocks_with for ch in target):
        return None

    owner = [-1] * m  # owner[b] = target position using block b

    def try_place(pos: int, seen: list[bool]) -> bool:
        for b in blocks_with[target[pos]]:
            if seen[b]:
                continue
            seen[b] = True
            if owner[b] == -1 or try_place(owner[b], seen):
                owner[b] = pos
                return True
        return False

    for pos in range(n):
        if not try_place(pos, [False] * m):
            return None

    used = [-1] * n
    for b, pos in enumerate(owner):
        if pos != -1:
            used[pos] = b
    return used


if __name__ == "__main__":
    assert can_form([["a", "b"], ["a"]], "ab")  # greedy would fail
    assert not can_form([["a", "b"]], "ab")
    assert can_form([["c", "a"], ["t", "a"], ["c", "x"]], "cat")
    assert not can_form([["a"], ["a"], ["b"]], "aabb")
    assert can_form([], "")
    assert not can_form([["x", "y"], ["x", "y"], ["x", "y"]], "xyz")
    assert not can_form([["a", "b"], ["a", "b"], ["c"]], "aaa")
    used = assign_blocks([["b", "o"], ["o", "k"], ["o"], ["b", "k"]], "book")
    assert used is not None and len(set(used)) == 4
    print("ok")

Complexity

Let n = len(target), B = len(blocks), S the total number of
characters across blocks, and E the number of (position, block) edges,
at most n * B.

• Building blocks_with: O(S) time and space.
• Matching: each of the n searches costs O(B + E) in the worst case,
  so O(n * (B + E)), bounded by O(n^2 * B). Hopcroft-Karp improves this
  to O(E * sqrt(n)).
• Letter-compressed max flow: at most 26 letter nodes, so the graph has
  O(26 * B) edges and the flow value is n; Dinic runs fast here even
  for a very long target.
• Space: O(S + B + n) for the index, owner, seen and the recursion
  stack (depth up to n; use an iterative DFS if n is large).

Test cases

• blocks=[["a","b"],["a"]], target="ab" -> True (block 1 for a,
  block 0 for b; greedy fails here).
• blocks=[["a","b"]], target="ab" -> False (one block, two letters).
• blocks=[["c","a"],["t","a"],["c","x"]], target="cat" -> True
  (c from block 2, a from block 0, t from block 1).
• blocks=[["a"],["a"],["b"]], target="aabb" -> False (more
  positions than blocks).
• blocks=[], target="" -> True (nothing to place).
• blocks=[["x","y"]]*3, target="xyz" -> False (no block has z).
• blocks=[["a","b"],["a","b"],["c"]], target="aaa" -> False (only
  two blocks have a).
• blocks=[["b","o"],["o","k"],["o"],["b","k"]], target="book" ->
  True (b:0 or 3, o:1/2, k:3/1; a valid assignment exists).
• A block with a repeated letter, [["a","a"]], target "aa" -> False
  (the block still counts once).

Follow-ups

1. Return which block is used for each position. assign_blocks
   already does it by inverting owner. Ask whether any valid answer is
   fine or a specific one (for example lexicographically smallest block
   indices), which needs a greedy-with-feasibility-check pass.
2. Many queries against the same blocks. Precompute blocks_with
   once. If queries are long and repetitive, switch to the
   26-letter-node flow so each query costs roughly O(26 * B) per unit of
   augmentation instead of depending on n.
3. Blocks can be used up to k times, or blocks come with a count.
   Give the block-to-sink edge capacity k (or the count) and run max
   flow instead of unit matching.
4. What is the longest prefix (or the most characters) you can form?
   Run the incremental Kuhn loop and stop at the first position that
   cannot be placed for the prefix. For the most characters in any
   positions, keep going and report the matching size.
5. Each block has a cost, minimize the total cost. This becomes the
   assignment problem: min-cost max flow, or Hungarian on the
   positions-by-blocks cost matrix.

Interviewer expectations

Mid-level (L4)

• Notices that greedy can fail and shows a counterexample, or at least
  writes a correct backtracking solution with pruning.
• Handles len(target) > len(blocks), missing letters, and repeated
  letters inside one block.
• Walks through a small example by hand and tests the code.

Senior (L5)

• Names the problem as bipartite matching and implements augmenting
  paths cleanly, with the per-search visited set.
• Explains why a failed augmenting path proves the answer is False.
• States complexity and mentions Hopcroft-Karp for large inputs.

Staff (L6+)

• Proposes the letter-compressed flow network and explains when it wins.
• Extends smoothly to capacities, costs, and repeated queries, choosing
  between matching, max flow, and min-cost flow with reasons.
• Raises practical limits: recursion depth, very large block sets, and
  how to precompute so a query service stays fast.