Guess the Word

Hard

#0797Time: 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).3 companies

Patterns

Math Game Theory

Data structures

Array String

Companies

Dropbox Verkada Verily

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Algorithm

1. Initialize a list possibleWords with all words from the input words.
1. Loop up to allowedGuesses times.
1. Select a random word guessWord from possibleWords.
1. Call master.guess(guessWord) to get the number of matches.
1. If matches is 6, the secret is found, so terminate.
1. Create a new list nextPossibleWords.
1. Iterate through each word in the current possibleWords list.
1. If the number of matches between word and guessWord is equal to the matches returned by the master, add word to nextPossibleWords.
1. Replace possibleWords with nextPossibleWords for the next iteration.

Walkthrough

The core idea is to prune the search space after every guess.

1/**2 * // This is the Master's API interface.3 * // You should not implement it, or speculate about its implementation4 * interface Master {5 *     public int guess(String word) {}6 * }7 */8class Solution {9    public void findSecretWord(String[] words, Master master) {10        List<String> possibleWords = new ArrayList<>(Arrays.asList(words));11        Random rand = new Random();12 13        for (int i = 0; i < 30; i++) { // At most 30 guesses allowed14            // Pick a random word from the current list of possibilities.15            String guessWord = possibleWords.get(rand.nextInt(possibleWords.size()));16            17            int matches = master.guess(guessWord);18            19            // If we found the secret word, we are done.20            if (matches == 6) {21                return;22            }23            24            // Filter the list of possible words.25            List<String> nextPossibleWords = new ArrayList<>();26            for (String word : possibleWords) {27                if (getMatches(guessWord, word) == matches) {28                    nextPossibleWords.add(word);29                }30            }31            possibleWords = nextPossibleWords;32        }33    }34    35    // Helper function to count matches between two words.36    private int getMatches(String word1, String word2) {37        int matches = 0;38        for (int i = 0; i < word1.length(); i++) {39            if (word1.charAt(i) == word2.charAt(i)) {40                matches++;41            }42        }43        return matches;44    }45}

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.

Complexity

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).

Trade-offs

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.

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.

Algorithm

1. Initialize a list possibleWords with all words from the input words.
1. Loop up to allowedGuesses times as long as possibleWords is not empty.
1. 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.
1. Call master.guess(bestGuess) to get the actual number of matches.
1. If matches is 6, the secret is found, so terminate.
1. Filter possibleWords to create a new list containing only words that have exactly matches with bestGuess.
1. Continue the loop with the new, smaller possibleWords list.

Walkthrough

The key is to select a guess word that is most effective at distinguishing between the remaining possibilities.

1/**2 * // This is the Master's API interface.3 * // You should not implement it, or speculate about its implementation4 * interface Master {5 *     public int guess(String word) {}6 * }7 */8class Solution {9    public void findSecretWord(String[] words, Master master) {10        List<String> possibleWords = new ArrayList<>(Arrays.asList(words));11 12        for (int i = 0; i < 30 && !possibleWords.isEmpty(); i++) {13            String guessWord = findBestGuess(possibleWords);14            int matches = master.guess(guessWord);15 16            if (matches == 6) {17                return;18            }19 20            List<String> nextPossibleWords = new ArrayList<>();21            for (String word : possibleWords) {22                if (getMatches(guessWord, word) == matches) {23                    nextPossibleWords.add(word);24                }25            }26            possibleWords = nextPossibleWords;27        }28    }29 30    private String findBestGuess(List<String> wordlist) {31        if (wordlist.size() <= 2) {32            return wordlist.get(0);33        }34        35        String bestGuess = null;36        int minMaxGroupSize = Integer.MAX_VALUE;37 38        for (String word1 : wordlist) {39            int[] groups = new int[7]; // groups[i] = count of words with i matches40            for (String word2 : wordlist) {41                if (word1.equals(word2)) continue;42                groups[getMatches(word1, word2)]++;43            }44            45            int maxGroupSize = 0;46            for (int size : groups) {47                if (size > maxGroupSize) {48                    maxGroupSize = size;49                }50            }51 52            if (maxGroupSize < minMaxGroupSize) {53                minMaxGroupSize = maxGroupSize;54                bestGuess = word1;55            }56        }57        return bestGuess;58    }59 60    private int getMatches(String word1, String word2) {61        int matches = 0;62        for (int i = 0; i < word1.length(); i++) {63            if (word1.charAt(i) == word2.charAt(i)) {64                matches++;65            }66        }67        return matches;68    }69}

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.

Complexity

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.

Trade-offs

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.

Solutions

Solution

1/** * // 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 ; } }

1// 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 ; } } };

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem