Stickers to Spell Word

Stickers to Spell Word

What is this problem about?

In the Stickers to Spell Word coding problem, you are given a set of stickers, each with a word on it, and a target word. You can use any number of stickers, and you can cut out individual letters from them. You want to find the minimum number of stickers needed to spell the target word. If it's impossible, return -1.

Why is this asked in interviews?

This "Hard" problem is common at Google and Meta. It tests a wide range of skills: string manipulation, frequency counting, and most importantly, optimization via Dynamic Programming or Memoization. It also introduces the concept of Bitmask interview pattern, as the state of the "target word" (which letters are already covered) can be represented as a bitmask.

Algorithmic pattern used

The most effective approach is BFS or DFS with Memoization, often using a Bitmask to represent the current state of the target word.

• State: A bitmask of length target.length(), where the $i$-th bit is 1 if the $i$-th character of the target is already covered.
• Transition: For each sticker, try applying it to the current state to see how many needed letters it can cover, leading to a new bitmask state.
• Optimization: Only use stickers that contain the first character of the current target that we still need. This pruning significantly reduces the search space.

Example explanation (use your own example)

Target: "apple", Stickers: ["app", "let"].

1. Current target: "apple" (mask 00000).
2. Use "app": Covers 'a', 'p', 'p'. New state: "??ple" (mask 11100).
3. From "??ple", use "let": Covers 'l', 'e'. New state: "??p??" (mask 11111).
4. Total stickers = 2. Wait, in this case "app" didn't cover the second 'p'. We would need another "app" sticker or a different one. The algorithm explores these combinations to find the minimum.

Common mistakes candidates make

• Greedy approach: Always picking the sticker with the most matching letters, which doesn't always lead to the global minimum.
• No pruning: Trying every sticker at every step, leading to an exponential time complexity that exceeds limits.
• Character reuse: Forgetting that each character on a sticker can only be used once for one character in the target.
• Ignoring "Impossible": Not handling cases where the target contains a letter that isn't on any sticker.

Interview preparation tip

Practice problems involving Bitmask, Dynamic Programming. These are common for tasks where you need to track the "coverage" of a small set of items (like the characters in a target word of length $\le 15$).