This is an interactive problem.

You are given an array of unique strings words where words[i] is six letters long. One word of words is chosen as secret.

You may call Master.guess(word) to guess a word. The guessed word should have type string and must be from the original array with 6 lowercase letters.

This function returns an integer representing the number of exact matches (value and position) of your guess to the secret word. Also, if your guess is not in the given wordlist, it will return -1 instead.

For each test case, you have exactly 10 guesses to guess the word. If you have made 10 or fewer calls to Master.guess and at least one of them was the secret, you pass the test case.

Thinking Process

  1. Elimination Strategy: Use match count to eliminate impossible candidates
  • Strings often need frequency maps or two-pointer scans.
  • Watch index bounds and empty-string edge cases.
  • Stack helps with nested or repeated patterns.
Array + hash map 2 7 11 map hash map for O(1) lookups

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Two pointers on string (this problem) O(n) O(1) Palindrome, parsing
Hash map / frequency O(n) O(k) Anagram, character counts
KMP / rolling hash O(n) O(n) Pattern matching
Stack parsing O(n) O(n) Decode string, parentheses

Examples

Example 1:

Input: secret = "acckzz", words = ["acckzz","ccbazz","eiowzz","abcczz"]
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"], numguesses = 10
Output: You guessed the secret word correctly.

Constraints

  • 1 <= words.length <= 100
  • words[i].length == 6
  • words[i] consist of lowercase English letters.
  • All the strings of words are unique.
  • secret exists in words.
  • numguesses == 10

Complexity

  • Time Complexity: O(n²) worst case - In worst case, we might check all words in each iteration, but typically much better due to filtering
  • Space Complexity: O(n) - For the candidate set

Optimization: Minimax Strategy

A more sophisticated approach is to pick the word that minimizes the maximum number of remaining candidates across all possible match counts:

# This is the Master's API interface.
# You should not implement it, or speculate about its implementation
class Master:
    def guess(self, word: str) -> int:
        pass


class Solution:
    def findSecretWord(self, words, master):
        cand = set(words)
        
        while cand:
            guess = next(iter(cand))
            
            matches = master.guess(guess)
            
            if matches == 6:
                return
            
            newCand = set()
            
            for s in words:
                if self.match(s, guess) == matches:
                    newCand.add(s)
            
            cand = newCand
    
    def match(self, a, b):
        cnt = 0
        
        for i in range(6):
            if a[i] == b[i]:
                cnt += 1
        
        return cnt

This strategy picks the word that, in the worst case, leaves the fewest remaining candidates, leading to faster convergence.

Common Mistakes

  • Skipping edge cases (empty input, single element, boundaries).
  • Off-by-one errors in loops and index ranges.
  • Forgetting to handle the case when no valid answer exists.

Key Takeaways

  1. Elimination Strategy: Use match count to eliminate impossible candidates
  2. Match Function: Count exact character matches at the same positions
  3. Filtering Logic: If match(word, guess) != matches, then word cannot be the secret
  4. Guaranteed Success: The algorithm will find the secret within 10 guesses since candidates are eliminated each round
  5. Word Selection: The current solution picks the first candidate, but more sophisticated strategies (like picking the word that minimizes maximum remaining candidates) can be used

References

Template Reference