How to Solve Stickers to Spell Word

This problem requires identifying the minimum number of stickers to form a target string by efficiently scanning arrays and tracking letters with hash tables. Start by converting each sticker into a frequency map, then recursively explore combinations while memoizing results for speed. The key is to avoid redundant searches and prune impossible paths early, leveraging the bitmask or array hash pattern inherent in sticker letter coverage.

Problem Statement

You are given a collection of n stickers, each containing a lowercase English word. Your goal is to spell out a given target string by cutting letters from these stickers and rearranging them. Stickers can be used multiple times, and each letter can be used only as many times as it appears in the sticker.

Return the minimum number of stickers needed to spell the target. If it is impossible to form the target from the available stickers, return -1. Constraints: 1 <= n <= 50, 1 <= sticker length <= 10, 1 <= target length <= 15.

Examples

Example 1

Input: stickers = ["with","example","science"], target = "thehat"

Output: 3

We can use 2 "with" stickers, and 1 "example" sticker. After cutting and rearrange the letters of those stickers, we can form the target "thehat". Also, this is the minimum number of stickers necessary to form the target string.

Example 2

Input: stickers = ["notice","possible"], target = "basicbasic"

Output: -1

We cannot form the target "basicbasic" from cutting letters from the given stickers.

Constraints

• n == stickers.length
• 1 <= n <= 50
• 1 <= stickers[i].length <= 10
• 1 <= target.length <= 15
• stickers[i] and target consist of lowercase English letters.

Solution Approach

Convert Stickers to Letter Frequency Maps

Scan each sticker and create a hash map of letter counts. This lets you quickly determine how many times each sticker can contribute to forming letters in the target, a core part of the array scanning plus hash lookup pattern.

Recursive Search with Memoization

Recursively attempt to build the target by subtracting letters covered by chosen stickers, storing intermediate results in a memoization table. This prevents redundant calculations and efficiently handles the combinatorial explosion of sticker selections.

Prune Irrelevant Stickers Early

For each recursion, skip stickers that do not contribute new letters to the remaining target. This leverages the input's sparsity and avoids unnecessary branches, a common failure mode when the search space grows too large.

Complexity Analysis

Time complexity is O(2^T * S * T), where T is the target length and S is the number of stickers, due to the recursive exploration of all target subsets with each sticker. Space complexity is O(2^T) for memoization storing subsets of the target.

What Interviewers Usually Probe

• Look for solutions using array scanning combined with hash maps to track letter frequencies.
• Expect candidates to discuss memoization to avoid repeated calculations in the combinatorial search.
• Watch for pruning strategies that reduce unnecessary recursive calls when stickers contribute no new letters.

Common Pitfalls or Variants

Common pitfalls

• Failing to memoize results, causing exponential time due to redundant recursive calls.
• Attempting to use each sticker only once rather than allowing multiple uses.
• Not pruning stickers that do not contribute to the remaining target, leading to wasted computation.

Follow-up variants

• Limiting the number of times each sticker can be used, requiring more careful counting.
• Target words with repeated letters appearing more than any single sticker can provide, testing aggregation logic.
• Stickers with overlapping letters where multiple sticker combinations yield the same target letters, challenging pruning strategies.

How GhostInterview Helps

• Provides a structured breakdown for mapping stickers into frequency arrays for fast lookups.
• Guides the user in implementing memoized recursion to efficiently handle the combinatorial search space.
• Highlights pruning opportunities and identifies which stickers contribute to remaining target letters to avoid wasted work.

Topic Pages

• Array
• Hash Table
• String
• Dynamic Programming
• Backtracking
• Bit Manipulation
• Memoization
• Bitmask

Related GhostInterview Pages

• LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
• Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
• How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.

FAQ

What is the main pattern used in Stickers to Spell Word?

The core pattern is array scanning plus hash lookup, using frequency maps of stickers to track letters and recursively cover the target.

Can each sticker be used multiple times?

Yes, each sticker can be reused infinitely, but you must account for its letter counts when forming the target.

Why is memoization important for this problem?

Memoization avoids recalculating the minimum stickers for the same remaining target, drastically reducing recursive calls and runtime.

What should I do if a target cannot be formed?

Return -1 immediately if no sticker combination can cover all letters of the target, as indicated by the recursive exploration.

How does pruning irrelevant stickers improve performance?

Skipping stickers that add no new letters prevents unnecessary recursive branches, reducing the combinatorial explosion inherent in exhaustive search.