Stickers to Spell Word - Practice Coding Problems

Stickers to Spell Word - Problem

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

We are given n different types of stickers. Each sticker has a lowercase English word on it.

You would like to spell out the given string target by cutting individual letters from your collection of stickers and rearranging them. You can use each sticker more than once if you want, and you have infinite quantities of each sticker.

Return the minimum number of stickers that you need to spell out target. If the task is impossible, return -1.

Note: In all test cases, all words were chosen randomly from the 1000 most common US English words, and target was chosen as a concatenation of two random words.

Input & Output

Example 1 — Basic Case

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

› Output: 3

💡 Note: We can use 2 "with" stickers (providing w,i,t,h each twice) and 1 "example" sticker (providing e,x,a,m,p,l,e) to get all letters: t,h,e,h,a,t requires 3 stickers total

Example 2 — Impossible Case

$ Input: stickers = ["notice","possible"], target = "basicxyz"

› Output: -1

💡 Note: The target contains 'x', 'y', 'z' which are not available in any sticker, making it impossible to spell

Example 3 — Single Sticker

$ Input: stickers = ["these","guess","about"], target = "test"

› Output: 2

💡 Note: Use "these" (t,h,e,s,e) and "guess" (g,u,e,s,s) to get t,e,s,t - need 2 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

Visualization

Tap to expand

Understanding the Visualization

Input

Given stickers and target word

Process

Find minimum stickers needed

Output

Return minimum count or -1

Key Takeaway

🎯 Key Insight: Use dynamic programming with character frequency states and memoization to find optimal solution

Asked in

G Google 25 a Amazon 20 M Microsoft 15 f Facebook 18

The key insight is to use dynamic programming with memoization to avoid recalculating the same target states. We represent each target state as a frequency count of remaining characters needed. The optimal approach uses BFS with memoization to find the minimum number of stickers. Time: O(2^n), Space: O(2^n)

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Backtracking	O(2^n)	O(n)	Try all possible combinations of stickers recursively without memoization
Optimized Memoization with BFS	O(2^n * m)	O(2^n)	Use BFS with memoization for optimal exploration order
Memoized Recursion	O(2^n)	O(2^n)	Add memoization to avoid recalculating the same subproblems

Recursive Backtracking — Algorithm Steps

Count frequency of each character in target
For each sticker, try using it and reduce target accordingly
Recursively solve for remaining characters
Return minimum stickers needed

Visualization

Tap to expand

Step-by-Step Walkthrough

Count Target

Count frequency of each character in target

Try Stickers

For each sticker, subtract its characters from target

Recurse

Recursively solve for remaining characters

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int charCount[26];
int stickerCounts[50][26];
int numStickers;

int min(int a, int b) {
    return a < b ? a : b;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int helper(int target[26]) {
    int hasRemaining = 0;
    for (int i = 0; i < 26; i++) {
        if (target[i] > 0) {
            hasRemaining = 1;
            break;
        }
    }
    if (!hasRemaining) return 0;
    
    int minStickers = INT_MAX;
    for (int i = 0; i < numStickers; i++) {
        int firstChar = -1;
        for (int j = 0; j < 26; j++) {
            if (stickerCounts[i][j] > 0) {
                firstChar = j;
                break;
            }
        }
        
        if (firstChar != -1 && target[firstChar] > 0) {
            int newTarget[26];
            for (int j = 0; j < 26; j++) {
                newTarget[j] = max(0, target[j] - stickerCounts[i][j]);
            }
            
            int result = helper(newTarget);
            if (result != -1) {
                minStickers = min(minStickers, 1 + result);
            }
        }
    }
    
    return minStickers == INT_MAX ? -1 : minStickers;
}

int solution(char stickers[][20], int n, char* target) {
    numStickers = n;
    
    // Count target characters
    int targetCount[26] = {0};
    for (int i = 0; target[i]; i++) {
        targetCount[target[i] - 'a']++;
    }
    
    // Count sticker characters
    for (int i = 0; i < n; i++) {
        memset(stickerCounts[i], 0, sizeof(stickerCounts[i]));
        for (int j = 0; stickers[i][j]; j++) {
            stickerCounts[i][stickers[i][j] - 'a']++;
        }
    }
    
    return helper(targetCount);
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    char stickers[50][20];
    int n = 0;
    
    char* token = strtok(line, "[],\"\n ");
    while (token != NULL) {
        strcpy(stickers[n], token);
        n++;
        token = strtok(NULL, "[],\"\n ");
    }
    
    char target[20];
    fgets(target, sizeof(target), stdin);
    target[strcspn(target, "\n")] = 0;
    
    printf("%d\n", solution(stickers, n, target));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Exponential combinations as we try all possible ways to use stickers

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion stack depth proportional to target length

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Backtracking — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler