Number of Valid Words for Each Puzzle - Practice Coding Problems

Number of Valid Words for Each Puzzle - Problem

Given an array of words and an array of puzzles, return an array answer where answer[i] is the number of words that are valid with respect to the puzzle puzzles[i].

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied:

word contains the first letter of puzzle.
For each letter in word, that letter is in puzzle.

For example, if the puzzle is "abcdefg", then valid words are "faced", "cabbage", and "baggage", while invalid words are "beefed" (does not include 'a') and "based" (includes 's' which is not in the puzzle).

Input & Output

Example 1 — Basic Case

$ Input: words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]

› Output: [1,1,3,2,4,0]

💡 Note: For puzzle "aboveyz": word "aaaa" contains 'a' and all letters are in puzzle, so count=1. For "abslute": words "able", "ability", "actt" are valid, so count=3.

Example 2 — Single Letters

$ Input: words = ["apple","pleas","please"], puzzles = ["aelpxy","aelpxy","aelpsxy"]

› Output: [0,1,3]

💡 Note: "apple" doesn't contain first letter 'a' from puzzle letters only. "pleas" is valid for second puzzle. All three words valid for third puzzle.

Example 3 — No Valid Words

$ Input: words = ["word","test"], puzzles = ["abcdef"]

› Output: [0]

💡 Note: Neither "word" nor "test" contains 'a' (first letter of puzzle), so no valid words.

Constraints

1 ≤ words.length ≤ 10⁵
4 ≤ words[i].length ≤ 50
1 ≤ puzzles.length ≤ 10⁴
puzzles[i].length == 7
words[i] and puzzles[i] consist of lowercase English letters
Each puzzles[i] contains unique characters

Visualization

Tap to expand

Understanding the Visualization

Input

Array of words and array of 7-character puzzles

Validation

Check: word contains first char of puzzle + all word chars in puzzle

Output

Count of valid words for each puzzle

Key Takeaway

🎯 Key Insight: Use bitmasks to represent character sets for O(1) subset checking instead of character-by-character comparison

Asked in

G Google 45 f Facebook 32 a Amazon 28

The key insight is using bit manipulation to represent character sets as bitmasks for efficient subset checking. Convert each word to a bitmask, then for each puzzle generate all submasks and count matching words that contain the first character. Best approach uses bit manipulation with Time: O(n × 2^7 + m), Space: O(m).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Character Matching	O(n × m × k)	O(1)	Check each word against each puzzle by comparing characters directly
Bit Manipulation with Bitmasks	O(n × 2^7 + m)	O(m)	Convert words and puzzles to bitmasks for efficient subset checking

Brute Force Character Matching — Algorithm Steps

For each puzzle, iterate through all words
Check if word contains puzzle's first character
Verify all word characters exist in puzzle

Visualization

Tap to expand

Step-by-Step Walkthrough

Check First Character

Verify word contains puzzle's first character

Validate All Characters

Check each character in word exists in puzzle

Count Valid Words

Increment counter for valid matches

Code -

solution.c — C

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

int* solution(char** words, int wordsSize, char** puzzles, int puzzlesSize, int* returnSize) {
    int* result = (int*)malloc(puzzlesSize * sizeof(int));
    *returnSize = puzzlesSize;
    
    for (int i = 0; i < puzzlesSize; i++) {
        int count = 0;
        bool puzzleChars[26] = {false};
        
        // Mark characters in puzzle
        for (int j = 0; puzzles[i][j]; j++) {
            puzzleChars[puzzles[i][j] - 'a'] = true;
        }
        char firstChar = puzzles[i][0];
        
        for (int w = 0; w < wordsSize; w++) {
            if (strchr(words[w], firstChar) != NULL) {
                bool valid = true;
                for (int j = 0; words[w][j] && valid; j++) {
                    if (!puzzleChars[words[w][j] - 'a']) {
                        valid = false;
                    }
                }
                if (valid) count++;
            }
        }
        
        result[i] = count;
    }
    
    return result;
}

int main() {
    // Simplified input parsing for demonstration
    char* words[] = {"aaaa", "asas", "able", "ability", "actt", "actor", "access"};
    char* puzzles[] = {"aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz"};
    
    int returnSize;
    int* result = solution(words, 7, puzzles, 6, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × m × k)

n puzzles × m words × k average character checks per word

✓ Linear Growth

Space Complexity

O(1)

Only using variables for counting, no extra data structures

✓ Linear Space

28.5K Views

Medium Frequency

~35 min Avg. Time

892 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

Brute Force Character Matching — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler