You are given an array of unique strings words where words[i] is six letters long. One word of words was chosen as a secret word.
You are also given the helper object Master. You may call Master.guess(word) where word is a six-letter-long string, and it must be from words. Master.guess(word) returns:
-1 if word is not from words, orThere is a parameter allowedGuesses for each test case where allowedGuesses is the maximum number of times you can call Master.guess(word).
For each test case, you should call Master.guess with the secret word without exceeding the maximum number of allowed guesses. You will get:
"Either you took too many guesses, or you did not find the secret word." if you called Master.guess more than allowedGuesses times or if you did not call Master.guess with the secret word, or"You guessed the secret word correctly." if you called Master.guess with the secret word with the number of calls to Master.guess less than or equal to allowedGuesses.The test cases are generated such that you can guess the secret word with a reasonable strategy (other than using the bruteforce method).
Example 1:
Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"], allowedGuesses = 10
Output: You guessed the secret word correctly.
Explanation:
master.guess("aaaaaa") returns -1, because "aaaaaa" is not in wordlist.
master.guess("acckzz") returns 6, because "acckzz" is secret and has all 6 matches.
master.guess("ccbazz") returns 3, because "ccbazz" has 3 matches.
master.guess("eiowzz") returns 2, because "eiowzz" has 2 matches.
master.guess("abcczz") returns 4, because "abcczz" has 4 matches.
We made 5 calls to master.guess, and one of them was the secret, so we pass the test case.
Example 2:
Input: secret = "hamada", words = ["hamada","khaled"], allowedGuesses = 10 Output: You guessed the secret word correctly. Explanation: Since there are two words, you can guess both.
Constraints:
1 <= words.length <= 100words[i].length == 6words[i] consist of lowercase English letters.wordlist are unique.secret exists in words.10 <= allowedGuesses <= 30#843 Guess the Word is an interactive problem where you must identify a hidden word from a given list using a limited number of guesses. Each guess returns the number of matching characters in the correct positions compared to the secret word. The challenge is choosing guesses that reduce the candidate space efficiently.
A common strategy is based on minimax reasoning. For every candidate word, simulate how it would partition the remaining words by the number of matching positions. Select the word that minimizes the size of the largest possible group of remaining candidates. This helps eliminate the most possibilities regardless of the feedback received.
After each call to guess(), filter the word list to keep only those with the same match count relative to the guessed word. Repeat this process until the secret is found or the guess limit is reached. Efficient implementations rely on precomputing pairwise match counts between words. Typical complexity is around O(N² × L) preprocessing with iterative filtering, where N is the number of words and L is the word length.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Minimax / Partition Strategy | O(N² × L) | O(N²) |
| Random Guess with Filtering | O(N × L) per round | O(N) |
Godfrey Twins
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
The difficulty comes from selecting guesses that maximize information rather than randomly trying words. Efficiently narrowing down the search space with limited queries requires strategic reasoning and careful pruning.
Yes, variations of interactive elimination and minimax-style problems appear in FAANG-style interviews. The problem tests reasoning about information gain, pruning search space, and handling interactive constraints.
Arrays or lists are typically used to store candidate words, while a matrix or cache can store pairwise match counts. This allows faster filtering and evaluation when applying the minimax strategy.
A common optimal strategy uses a minimax approach. For each candidate word, calculate how it partitions the remaining possibilities by match count and choose the guess that minimizes the worst-case remaining group size.