Guess the Word - Solution & Explanation

Problem Overview: You receive a list of possible 6-letter words. One of them is the secret. Each guess returns the number of characters that match the secret word at the same position. The goal is to identify the secret word within 10 guesses by strategically choosing which word to query.

Approach 1: Minimax Strategy (O(n^2 * L) time, O(n) space)

This approach treats the problem like an adversarial game. For every candidate word in the list, compute how it partitions the remaining words based on the number of positional matches (0–6). The worst-case bucket size after a guess represents how much uncertainty remains. The minimax rule picks the word whose largest bucket is smallest, minimizing the worst-case remaining candidates. Implementation typically builds a frequency array for match counts and chooses the guess with the smallest maximum partition. After each guess, filter the word list to keep only words that produce the same match count with the guess as reported by Master.guess(). This process continues until the secret is found or guesses are exhausted. Time complexity is O(n^2 * L) because each pair of words may be compared to count matches (with L = 6), and space complexity is O(n) for maintaining candidate lists. This approach relies heavily on efficient comparison logic and careful pruning of the candidate set.

Approach 2: Randomized Guessing with Strategy (O(n^2 * L) expected time, O(n) space)

A simpler alternative randomly selects a word from the remaining candidates and uses the returned match count to eliminate inconsistent words. After a guess, iterate through the word list and keep only those words whose positional match count with the guessed word equals the response from the master API. The filtering step ensures the candidate pool shrinks every round. Although the selection is random, repeated filtering often converges quickly because the search space drops sharply after each guess. Expected complexity remains around O(n^2 * L) due to repeated comparisons during filtering. This method is easier to implement and often passes constraints, but it lacks the worst-case guarantees provided by the minimax approach.

Both approaches rely on repeatedly comparing words character-by-character and maintaining a shrinking candidate set, which makes the problem closely related to techniques from array processing and string comparison. The decision strategy—especially in the minimax version—mirrors concepts from game theory, where you minimize the opponent's best outcome.

Recommended for interviews: The minimax strategy is the expected solution. It demonstrates the ability to reason about worst-case partitions and adversarial search spaces. A randomized filtering approach can show initial understanding, but the minimax strategy signals stronger algorithmic thinking and better control over worst-case behavior.