# Guess the Word
**Difficulty:** HARD
[External](https://leetcode.com/problems/guess-the-word)
Canonical: https://scaleengineer.com/dsa/problems/guess-the-word
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** Array, String
**Companies:** [Dropbox](https://scaleengineer.com/companies/dropbox), [Verkada](https://scaleengineer.com/companies/verkada), [Verily](https://scaleengineer.com/companies/verily)
---
## Problem
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`, or
* an integer representing the number of exact matches (value and position) of your guess to the secret word.

There 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 <= 100`
* `words[i].length == 6`
* `words[i]` consist of lowercase English letters.
* All the strings of `wordlist` are **unique**.
* `secret` exists in `words`.
* `10 <= allowedGuesses <= 30`

# Approaches
## Simple Elimination with Random Guess
This approach works by iteratively reducing the pool of possible secret words. We start with the entire word list. In each step, we pick a word from the current pool, guess it, and get the number of matching characters from the `Master` interface. This information is then used to filter the pool, keeping only the words that have the same number of matches with our guessed word. The process repeats with the smaller pool until the secret word is found.
**Time:** O(G * N * L), where G is the number of guesses made (at most `allowedGuesses`), N is the initial number of words, and L is the length of each word. In each guess, we iterate through the current list of possible words (at most N) and compare each with the guessed word (which takes O(L) time). · **Space:** O(N * L) to store the list of possible words. In each iteration, a new list is created, but the old one is discarded, so the peak space usage remains O(N * L).
**Pros:** Simpler to implement than more advanced strategies.; Effectively reduces the search space compared to a brute-force approach.
**Cons:** The random selection of the guess word is not optimal.; It may fail to find the secret word within the allowed number of guesses if a series of unlucky random choices are made.
### Explanation
The core idea is to prune the search space after every guess.
```java
/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface Master {
 *     public int guess(String word) {}
 * }
 */
class Solution {
    public void findSecretWord(String[] words, Master master) {
        List<String> possibleWords = new ArrayList<>(Arrays.asList(words));
        Random rand = new Random();

        for (int i = 0; i < 30; i++) { // At most 30 guesses allowed
            // Pick a random word from the current list of possibilities.
            String guessWord = possibleWords.get(rand.nextInt(possibleWords.size()));
            
            int matches = master.guess(guessWord);
            
            // If we found the secret word, we are done.
            if (matches == 6) {
                return;
            }
            
            // Filter the list of possible words.
            List<String> nextPossibleWords = new ArrayList<>();
            for (String word : possibleWords) {
                if (getMatches(guessWord, word) == matches) {
                    nextPossibleWords.add(word);
                }
            }
            possibleWords = nextPossibleWords;
        }
    }
    
    // Helper function to count matches between two words.
    private int getMatches(String word1, String word2) {
        int matches = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) == word2.charAt(i)) {
                matches++;
            }
        }
        return matches;
    }
}
```
The choice of the guess word is crucial. In this simple version, we pick a word randomly from the current set of candidates. While this is better than blind guessing, it's not optimal. A poorly chosen guess might not significantly reduce the size of the candidate list, risking exceeding the `allowedGuesses` limit.
### Algorithm
- 1. Initialize a list `possibleWords` with all words from the input `words`.
- 2. Loop up to `allowedGuesses` times.
- 3. Select a random word `guessWord` from `possibleWords`.
- 4. Call `master.guess(guessWord)` to get the number of `matches`.
- 5. If `matches` is 6, the secret is found, so terminate.
- 6. Create a new list `nextPossibleWords`.
- 7. Iterate through each `word` in the current `possibleWords` list.
- 8. If the number of matches between `word` and `guessWord` is equal to the `matches` returned by the master, add `word` to `nextPossibleWords`.
- 9. Replace `possibleWords` with `nextPossibleWords` for the next iteration.

## Minimax Elimination Strategy
This approach refines the elimination strategy by making the smartest possible guess at each step. The 'smartest' guess is the one that minimizes the size of the candidate list in the worst-case scenario. To find this guess, we evaluate every word in the current candidate list. For each potential guess, we calculate how it would partition the other candidates based on the number of matches (0 to 6). We then choose the word that minimizes the size of the largest resulting partition. This minimax strategy guarantees the most significant reduction of the search space, regardless of the master's feedback.
**Time:** O(G * N^2 * L), where G is the number of guesses (at most `allowedGuesses`), N is the number of words in the current list, and L is the word length. The dominant operation is `findBestGuess`, which involves a nested loop over the `possibleWords` list (O(N^2)) and a string comparison inside (O(L)). This is performed for each guess. · **Space:** O(N * L) to store the list of possible words. The `groups` array in `findBestGuess` uses constant space O(1) as the word length is fixed.
**Pros:** Optimal strategy in terms of minimizing the number of guesses required in the worst case.; Guaranteed to find the solution within the given constraints due to its efficient pruning of the search space.
**Cons:** Higher computational cost per guess (O(N^2 * L)) compared to simpler strategies.
### Explanation
The key is to select a guess word that is most effective at distinguishing between the remaining possibilities.
```java
/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * interface Master {
 *     public int guess(String word) {}
 * }
 */
class Solution {
    public void findSecretWord(String[] words, Master master) {
        List<String> possibleWords = new ArrayList<>(Arrays.asList(words));

        for (int i = 0; i < 30 && !possibleWords.isEmpty(); i++) {
            String guessWord = findBestGuess(possibleWords);
            int matches = master.guess(guessWord);

            if (matches == 6) {
                return;
            }

            List<String> nextPossibleWords = new ArrayList<>();
            for (String word : possibleWords) {
                if (getMatches(guessWord, word) == matches) {
                    nextPossibleWords.add(word);
                }
            }
            possibleWords = nextPossibleWords;
        }
    }

    private String findBestGuess(List<String> wordlist) {
        if (wordlist.size() <= 2) {
            return wordlist.get(0);
        }
        
        String bestGuess = null;
        int minMaxGroupSize = Integer.MAX_VALUE;

        for (String word1 : wordlist) {
            int[] groups = new int[7]; // groups[i] = count of words with i matches
            for (String word2 : wordlist) {
                if (word1.equals(word2)) continue;
                groups[getMatches(word1, word2)]++;
            }
            
            int maxGroupSize = 0;
            for (int size : groups) {
                if (size > maxGroupSize) {
                    maxGroupSize = size;
                }
            }

            if (maxGroupSize < minMaxGroupSize) {
                minMaxGroupSize = maxGroupSize;
                bestGuess = word1;
            }
        }
        return bestGuess;
    }

    private int getMatches(String word1, String word2) {
        int matches = 0;
        for (int i = 0; i < word1.length(); i++) {
            if (word1.charAt(i) == word2.charAt(i)) {
                matches++;
            }
        }
        return matches;
    }
}
```
The `findBestGuess` function is the core of this strategy. It iterates through every candidate `word1` and simulates guessing it. For each `word1`, it checks against every other candidate `word2` to see how they would be grouped by match count. The goal is to find a `word1` where the largest of these groups is as small as possible. This ensures that even in the worst case (where the secret lies in the largest group), we have pruned the search space effectively.
### Algorithm
- 1. Initialize a list `possibleWords` with all words from the input `words`.
- 2. Loop up to `allowedGuesses` times as long as `possibleWords` is not empty.
- 3. **Find the best guess:**
-    a. For each `word1` in `possibleWords`, calculate how it partitions the list.
-    b. To do this, create a frequency map (or an array `groups` of size 7).
-    c. For each `word2` in `possibleWords`, calculate `matches = getMatches(word1, word2)` and increment `groups[matches]`.
-    d. Find the maximum value in `groups`. This is the worst-case size of the next candidate list if we guess `word1`.
-    e. Keep track of the `word1` that results in the minimum worst-case size. This is our `bestGuess`.
- 4. Call `master.guess(bestGuess)` to get the actual number of `matches`.
- 5. If `matches` is 6, the secret is found, so terminate.
- 6. Filter `possibleWords` to create a new list containing only words that have exactly `matches` with `bestGuess`.
- 7. Continue the loop with the new, smaller `possibleWords` list.

# Solutions
### Java

```java
/** * // This is the Master's API interface. * // You should not implement it, or speculate about its implementation * interface Master { * public int guess(String word) {} * } */ class Solution { public void findSecretWord ( String [] wordlist , Master master ) { int length = wordlist . length ; int [][] sameCounts = new int [ length ][ length ]; for ( int i = 0 ; i < length ; i ++) sameCounts [ i ][ i ] = 6 ; for ( int i = 0 ; i < length ; i ++) { String word1 = wordlist [ i ]; for ( int j = i + 1 ; j < length ; j ++) { String word2 = wordlist [ j ]; sameCounts [ i ][ j ] = sameCount ( word1 , word2 ); sameCounts [ j ][ i ] = sameCounts [ i ][ j ]; } } boolean [] candidates = new boolean [ length ]; Arrays . fill ( candidates , true ); int index = 0 ; while ( index >= 0 && index < length ) { index = findNext ( sameCounts , candidates ); if ( index < 0 ) break ; int guessResult = master . guess ( wordlist [ index ]); if ( guessResult == 6 ) break ; for ( int i = 0 ; i < length ; i ++) { if ( candidates [ i ] && sameCounts [ index ][ i ] != guessResult ) candidates [ i ] = false ; } } } public int sameCount ( String word1 , String word2 ) { int count = 0 ; for ( int i = 0 ; i < 6 ; i ++) { if ( word1 . charAt ( i ) == word2 . charAt ( i )) count ++; } return count ; } public int findNext ( int [][] sameCounts , boolean [] candidates ) { int length = candidates . length ; int min = Integer . MAX_VALUE ; int minIndex = - 1 ; for ( int i = 0 ; i < length ; i ++) { if ( candidates [ i ]) { int [] counts = new int [ 7 ]; for ( int j = 0 ; j < length ; j ++) { if ( j != i && candidates [ j ]) { int count = sameCounts [ i ][ j ]; counts [ count ]++; } } int max = 0 ; for ( int num : counts ) max = Math . max ( max , num ); if ( max < min ) { min = max ; minIndex = i ; } } } return minIndex ; } }
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/guess-the-word/ // Time: O(N) // Space: O(1) class Solution { int countSame ( string & a , string & b ) { int cnt = 0 ; for ( int i = 0 ; i < 6 ; ++ i ) cnt += a [ i ] == b [ i ]; return cnt ; } public: void findSecretWord ( vector < string >& A , Master & master ) { int N = A . size (); while ( true ) { string w = A [ rand () % N ]; int cnt = master . guess ( w ), len = 0 ; if ( cnt == 6 ) break ; for ( int i = 0 ; i < N ; ++ i ) { if ( countSame ( A [ i ], w ) == cnt ) swap ( A [ i ], A [ len ++ ]); } N = len ; } } };
```