Spelling Bee Word Finder

Overview

The problem asks us to filter a dictionary based on three specific constraints reminiscent of the popular "Spelling Bee" word game. We need to identify words that are long enough (at least 4 characters), include a mandatory "center" letter, and are composed exclusively of a restricted set of allowed characters.

The core of the challenge lies in efficiently checking these character-based constraints for each word in a potentially large dictionary.

Brute Force

In a brute-force approach, we iterate through every word in the dictionary and verify the three rules sequentially. For the character set constraint, we can check every character of each word to see if it exists in the combined list of requiredLetter and optionalLetters.

def find_valid_words(requiredLetter: str, optionalLetters: list[str], dictionary: list[str]) -> list[str]:
    valid_words = []
    
    # Combine allowed letters into a single list/string for searching
    allowed = [requiredLetter] + optionalLetters
    
    for word in dictionary:
        # Rule 1: Minimum length of 4
        if len(word) < 4:
            continue
            
        # Rule 2: Must contain the required letter
        if requiredLetter not in word:
            continue
            
        # Rule 3: All characters must be in the allowed set
        is_valid = True
        for char in word:
            if char not in allowed:
                is_valid = False
                break
        
        if is_valid:
            valid_words.append(word)
            
    return valid_words

Time complexity: O(N * L * M) — Where N is the number of words, L is the average length of a word, and M is the number of allowed letters (due to 'in' checks on a list). Space complexity: O(N * L) — To store and return the list of valid words.

Optimal / Best Approach

The bottleneck in the brute-force approach is checking if every character in a word exists in the allowed list repeatedly. We can optimize this by using a Set for the allowed characters, which provides $O(1)$ average-time lookups.

Furthermore, we can use Set Theory to simplify the logic: a word is valid (for rule 3) if the set of unique characters in the word is a subset of the set of allowed characters.

def find_valid_words(requiredLetter: str, optionalLetters: list[str], dictionary: list[str]) -> list[str]:
    # Use a set for O(1) lookups and subset operations
    allowed_set = set(optionalLetters)
    allowed_set.add(requiredLetter)
    
    result = []
    
    for word in dictionary:
        # Rule 1: Length check is O(1) in Python
        if len(word) < 4:
            continue
            
        # Rule 2: Required letter check
        if requiredLetter not in word:
            continue
            
        # Rule 3: Character composition check
        # 'set(word) <= allowed_set' checks if all chars in word are in allowed_set
        if set(word).issubset(allowed_set):
            result.append(word)
            
    return result

Time complexity: O(N * L) — We iterate through N words, and for each word, we perform operations proportional to its length L (creating a set and checking subset/containment). Space complexity: O(M + (N * L)) — We store M allowed characters in a set, plus the space required for the output list of valid words.

Why this works

1. Set Lookups: Converting optionalLetters and requiredLetter into a single set transforms a linear search $O(M)$ into a constant time $O(1)$ operation.
2. Subset Property: The condition that a word must only contain letters from the allowed list is mathematically equivalent to saying the set of characters in the word is a subset of the allowed characters.
3. Short-Circuiting: By checking the length and the requiredLetter first, we avoid the overhead of set creation for words that are already disqualified by simpler rules.

Fast