Stickers to Spell Word Solution in C++

Problem Description

So, you want to spell a word using stickers? Sounds easy, right? Well, welcome to the world of “Stickers to Spell Word,” where your dreams of crafting the perfect message are thwarted by the limitations of your sticker collection. Imagine you have a bunch of stickers with letters on them, but they’re not exactly the letters you need. It’s like trying to write a love letter with only “X” and “O” stickers—good luck with that!

In this problem, you are given a list of stickers, each containing a collection of letters, and a target word that you want to spell out. Your mission, should you choose to accept it, is to determine the minimum number of stickers required to spell out the target word. If it’s impossible, you’ll be left with nothing but a sad face emoji. 😢

Code Solution


class Solution {
 public:
  int minStickers(vector& stickers, string target) {
    const int n = target.size();
    const int maxMask = 1 << n;
    vector dp(maxMask, INT_MAX);
    dp[0] = 0;

    for (int mask = 0; mask < maxMask; ++mask) {
      if (dp[mask] == INT_MAX)
        continue;
      for (const string& sticker : stickers) {
        int superMask = mask;
        for (const char c : sticker)
          for (int i = 0; i < n; ++i)
            if (c == target[i] && (superMask >> i & 1) == 0) {
              superMask |= 1 << i;
              break;
            }
        dp[superMask] = min(dp[superMask], dp[mask] + 1);
      }
    }

    return dp.back() == INT_MAX ? -1 : dp.back();
  }
};

Approach

The approach taken in this solution is a classic dynamic programming technique. We use a bitmask to represent the letters in the target word that we have already covered. The dp array keeps track of the minimum number of stickers needed to achieve each state represented by the bitmask. For each sticker, we attempt to expand our current state by checking which letters we can cover and updating our dp array accordingly. It’s like playing a game of Tetris, but instead of blocks, you’re fitting letters into your word!

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(n * m * 2ⁿ)
Space Complexity	O(2ⁿ)

Real-World Example

Imagine you’re throwing a birthday party and you want to create a banner that says “Happy Birthday!” But all you have are stickers that say “H”, “A”, “P”, “Y”, “B”, “I”, “R”, “T”, “D”, and “!”—but no “H” or “A” stickers! You’ll need to figure out how to combine your limited resources (stickers) to create the perfect birthday message. This problem is a fun way to think about resource management and optimization in real life!