691. Stickers to Spell Word

📝 Problem Details

• Title: 691. Stickers to Spell Word
• Link: https://leetcode.com/problems/stickers-to-spell-word/
• Difficulty: Hard
• Tags/Categories: Dynamic-Programming Memoization Top-Down State-Transition Strings DFS

💭What Were My Initial Thoughts?

- use a hash map to store the character frequencies for target
- this feels like a greedy problem since we are going to be constantly searching for the lowest number of stickers to form our string
- DP may be useful here since we need a way of tracking overlapping uses of stickers since they can be reused
- maybe something that tracks for a given sticker, what chars it contains

🤔What Did I Struggle With?

- what to do after preprocessing stickers into frequency maps
- actioning my assumption of the problem being DP
- defining the state/

💡 Explanation of Solution

- preprocess stickers into frequency maps
- use remaining string as the state
- apply stickers recursively, reducing remaining
- memoize results to avoid recomputation
- return the minimum stickers needed or -1 if impossible

⌛ Complexity Analysis

💻 Implementation of Solution

class Solution {
private:
	vector<vector<int>> stickerCount;
	unordered_map<string, int> memo;
 
	int dfs(string remaining) {
		// check if the result for this state is already computed 
		if(memo.count(remaining)) return memo[remaining];
 
		// count character frequencies in the current target state
		vector<int> targetCount(26,0);
		for(char ch : remaining) {
			targetCount[ch - 'a']++;
		}
 
		int result = INT_MAX; // we are attempting to minimize result during dfs
 
		// try each sticker to reduce the target 
		for(const vector<int>& sticker : stickerCount) {
			// skip stickers that don't contribute to the first character of remaining
			if (sticker[remaining[0] - 'a'] == 0) continue;
			
			string nextRemaining;
			for(int i = 0; i < 26; i++) {
				if(targetCount[i] > 0) {
					int remainingCount = targetCount[i] - sticker[i];
					if(remainingCount > 0) 
						nextRemaining += string(remainingCount, 'a' + i);
				}
			}
 
			// recursively solve for the next state
			int subproblem = dfs(nextRemaining);
			if(subproblem != -1)
				result = min(result, 1 + subproblem);
		}
 
		// memoize and return the result for the current state
		memo[remaining] = (result == INT_MAX ? -1 : result);
		return memo[remaining];
	}
public:
	int minStickers(vector<string>& stickers, string target) {
		int n = target.size();
		memo.clear();
		memo[""] = 0; // base case : no target rquires - stickers
 
		// proprocess stickers into frequency maps
		for(const string& sticker : stickers) {
			vector<int> count(26,0);
			for(char ch : sticker) {
				count[ch - 'a']++;
			}
			stickerCount.push_back(count);
		}
 
		// cal DFS with the initial target
		return dfs(target);
	}
};