843. Guess the Word - Solution & Explanation

Q: Is Guess the Word easy or hard?

Guess the Word is classified as a Hard problem on LeetCode. The difficulty comes from designing a strategy that consistently finds the secret within 10 guesses. Implementing the minimax partition logic and reasoning about worst-case reductions makes it significantly more complex than typical string problems.

Q: How to solve Guess the Word efficiently?

Use a minimax-style selection strategy. For every candidate word, simulate how it partitions the remaining words by match count. Pick the word whose worst-case partition is smallest, then filter the candidate list using the feedback from the interactive guess. This ensures the search space shrinks quickly.

Q: What is the best approach for Guess the Word?

The minimax strategy is the most reliable approach. For each possible guess, group the remaining candidate words by how many characters match. Choose the word that minimizes the largest group in the worst case. This keeps the candidate space shrinking efficiently and guarantees strong performance within the 10-guess limit.

Q: What data structure is used in Guess the Word?

The solution mainly uses arrays or lists to maintain candidate words and frequency arrays to track match-count partitions. String comparison functions compute positional matches between two words. The overall strategy relies on filtering and grouping operations on these collections.

Q: What is the time complexity of Guess the Word?

Most optimized solutions run in O(n^2 * L) time, where n is the number of candidate words and L is the word length (6). The algorithm compares pairs of words to calculate positional matches and repeatedly filters the candidate list after each guess. Space complexity is O(n) for storing remaining candidates.

Q: Is Guess the Word asked at Google, Amazon, or Meta?

Guess the Word is commonly associated with Google-style interview problems because it combines interactive APIs, elimination strategies, and adversarial reasoning. Similar guessing and information-reduction problems appear in interviews at major tech companies including Google and Meta.

Q: Is there a Python or Java solution for Guess the Word?

Solutions are commonly implemented in Python, Java, C++, and JavaScript. Each implementation follows the same pattern: compute match counts between words, select the next guess using either minimax or random strategy, and filter the remaining candidate list based on the interactive response.

The 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

Approach overview

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.

Approach 1: Approach 1: Minimax Strategy

In this approach, we utilize a minimax strategy to minimize the possible size of the word list with each guess. For every guess, we divide the list based on the number of matches it has with other words in the list. The goal is to eliminate as many potential candidates as possible with each guess to find the secret word more efficiently.

Python

class Solution:
    def findSecretWord(self, words, master):
        import random
        def match(word1, word2):
            return sum(c1 == c2 for c1, c2 in zip(word1, word2))

        n = len(words)
        for _ in range(10):
            count = [0] * n
            for i in range(n):
                for j in range(n):
                    if i != j:
                        count[i] += match(words[i], words[j])

            guess_index = min(range(n), key=lambda i: -count[i])
            matches = master.guess(words[guess_index])
            words = [word for word in words if match(word, words[guess_index]) == matches]

Java

import java.util.List;

interface Master {
    int guess(String word);
}

public class Solution {
    private int match(String a, String b) {
        int matches = 0;
        for (int i = 0; i < 6; i++) {
            if (a.charAt(i) == b.charAt(i)) matches++;
        }
        return matches;
    }

    public void findSecretWord(String[] words, Master master) {
        for (int tries = 0; tries < 10; tries++) {
            int count[] = new int[words.length];
            for (int i = 0; i < words.length; i++)
                for (int j = 0; j < words.length; j++)
                    if (i != j) count[i] += match(words[i], words[j]);

            int guessIndex = 0;
            for (int i = 0; i < words.length; i++)
                if (count[i] < count[guessIndex])
                    guessIndex = i;
            int matches = master.guess(words[guessIndex]);
            List<String> newWords = new ArrayList<>();
            for (String word : words)
                if (match(word, words[guessIndex]) == matches)
                    newWords.add(word);
            words = newWords.toArray(new String[0]);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>

using namespace std;

class Master {
public:
    int guess(string word);
};

class Solution {
public:
    int match(const string &a, const string &b) {
        int matches = 0;
        for (int i = 0; i < 6; ++i) {
            if (a[i] == b[i]) ++matches;
        }
        return matches;
    }

    void findSecretWord(vector<string>& words, Master& master) {
        for (int _ = 0; _ < 10; ++_) {
            vector<int> count(words.size(), 0);
            for (int i = 0; i < words.size(); ++i)
                for (int j = i + 1; j < words.size(); ++j)
                    if (i != j) count[i] += match(words[i], words[j]);

            int guess_index = min_element(count.begin(), count.end()) - count.begin();
            int matches = master.guess(words[guess_index]);
            vector<string> new_words;
            for (string& word : words)
                if (match(word, words[guess_index]) == matches)
                    new_words.push_back(word);
            words = std::move(new_words);
        }
    }
};

JavaScript

class Solution {
    findSecretWord(words, master) {
        const match = (w1, w2) => w1.split('').filter((c, i) => c === w2[i]).length;

        for (let tries = 0; tries < 10; tries++) {
            const count = Array(words.length).fill(0);
            for (let i = 0; i < words.length; i++) {
                for (let j = 0; j < words.length; j++) {
                    if (i !== j) {
                        count[i] += match(words[i], words[j]);
                    }
                }
            }
            let guessIndex = count.indexOf(Math.min(...count));
            let matches = master.guess(words[guessIndex]);
            words = words.filter(word => match(word, words[guessIndex]) === matches);
        }
    }
}

#include <stdio.h>
#include <string.h>

int match(const char* a, const char* b) {
    int matches = 0;
    for (int i = 0; i < 6; ++i) 
        if (a[i] == b[i]) matches++;
    return matches;
}

void findSecretWord(const char* words[], int n, int (*guess)(const char*)) {
    for (int attempt = 0; attempt < 10; ++attempt) {
        int count[n];
        memset(count, 0, sizeof(count));
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                if (i != j) count[i] += match(words[i], words[j]);

        int guess_index = 0;
        for (int i = 0; i < n; ++i)
            if (count[i] > count[guess_index]) guess_index = i;

        int matches = guess(words[guess_index]);
        int new_size = 0;
        for (int i = 0; i < n; ++i)
            if (match(words[i], words[guess_index]) == matches)
                words[new_size++] = words[i];

        n = new_size;
    }
}

public class Solution {
    public void FindSecretWord(string[] words, Master master) {
        int Match(string a, string b) {
            int matches = 0;
            for (int i = 0; i < a.Length; i++) {
                if (a[i] == b[i]) matches++;
            }
            return matches;
        }

        for (int attempts = 0; attempts < 10; attempts++) {
            int[] count = new int[words.Length];
            for (int i = 0; i < words.Length; i++)
                for (int j = 0; j < words.Length; j++)
                    if (i != j) count[i] += Match(words[i], words[j]);

            int guessIndex = 0;
            for (int i = 0; i < words.Length; i++)
                if (count[i] < count[guessIndex])
                    guessIndex = i;

            int matches = master.Guess(words[guessIndex]);
            var newWords = new List<string>();
            foreach (string word in words) {
                if (Match(word, words[guessIndex]) == matches)
                    newWords.Add(word);
            }
            words = newWords.ToArray();
        }
    }
}

We first count matches between each pair of words and use a heuristic to maximize the minimum size of the elimination set. The strategy involves selecting the word which, when guessed, minimizes the worst-case number of words remaining in the list.

Complexity

Time Complexity: O(N^2) where N is the number of words. Space Complexity: O(N).

Try this approach in the editor

Approach 2: Approach 2: Randomized Guessing with Strategy

An alternative approach involves a randomized method that guesses based on the frequency of word intersections. Utilize a strategy that considers how often words share the same characters positionally, choosing those guesses that maximize intersection frequencies to steadily isolate the secret word.

Python

class Solution:
    def findSecretWord(self, words, master):
        import random

        def match(w1, w2):
            return sum(x == y for x, y in zip(w1, w2))

        for _ in range(10):
            guess_word = random.choice(words)
            matches = master.guess(guess_word)
            words = [w for w in words if match(guess_word, w) == matches]

Java

import java.util.Random;

interface Master {
    int guess(String word);
}

public class Solution {
    private int match(String a, String b) {
        int matches = 0;
        for (int i = 0; i < 6; i++) {
            if (a.charAt(i) == b.charAt(i)) matches++;
        }
        return matches;
    }

    public void findSecretWord(String[] words, Master master) {
        Random rand = new Random();
        for (int attempts = 0; attempts < 10; attempts++) {
            String guessWord = words[rand.nextInt(words.length)];
            int matches = master.guess(guessWord);
            words = Arrays.stream(words)
                    .filter(word -> match(word, guessWord) == matches)
                    .toArray(String[]::new);
        }
    }
}

C++

#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>

using namespace std;

class Master {
public:
    int guess(string word);
};

class Solution {
public:
    int match(const string &a, const string &b) {
        int matches = 0;
        for (int i = 0; i < 6; ++i) {
            if (a[i] == b[i]) ++matches;
        }
        return matches;
    }

    void findSecretWord(vector<string>& words, Master& master) {
        for (int attempt = 0; attempt < 10; ++attempt) {
            string guess_word = words[rand() % words.size()];
            int matches = master.guess(guess_word);
            vector<string> new_words;
            for (const string& word : words) {
                if (match(word, guess_word) == matches) {
                    new_words.push_back(word);
                }
            }
            words = std::move(new_words);
        }
    }
};

JavaScript

class Solution {
    findSecretWord(words, master) {
        const match = (a, b) => {
            let matches = 0;
            for (let i = 0; i < a.length; i++)
                if (a[i] === b[i]) matches++;
            return matches;
        };

        for (let tries = 0; tries < 10; tries++) {
            const guessWord = words[Math.floor(Math.random() * words.length)];
            const matches = master.guess(guessWord);
            words = words.filter(w => match(w, guessWord) === matches);
        }
    }
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int match(const char* a, const char* b) {
    int matches = 0;
    for (int i = 0; i < 6; ++i) 
        if (a[i] == b[i]) matches++;
    return matches;
}

void findSecretWord(char* words[], int n, int (*guess)(const char*)) {
    for (int attempt = 0; attempt < 10; ++attempt) {
        int rand_index = rand() % n;
        const char* guess_word = words[rand_index];
        int matches = guess(guess_word);
        int new_n = 0;
        for (int i = 0; i < n; ++i)
            if (match(words[i], guess_word) == matches)
                words[new_n++] = words[i];
        n = new_n;
    }
}

public class Solution {
    public void FindSecretWord(string[] words, Master master) {
        int Match(string a, string b) {
            int matches = 0;
            for (int i = 0; i < a.Length; i++) {
                if (a[i] == b[i]) matches++;
            }
            return matches;
        }

        for (int attempts = 0; attempts < 10; attempts++) {
            var rand = new Random();
            string guessWord = words[rand.Next(words.Length)];
            int matches = master.Guess(guessWord);
            words = Array.FindAll(words, word => Match(word, guessWord) == matches);
        }
    }
}

This Python solution randomly selects a word and guesses it. It only keeps words that have the same matching character count as reported by the guess to continuously narrow down the possibilities.

Complexity

Time Complexity: O(N) for each guess where N is the length of words. Space Complexity: O(N) for maintaining words.

Try this approach in the editor

Complexity comparison

Approach	Complexity
Approach 1: Minimax Strategy	Time Complexity: O(N^2) where N is the number of words. Space Complexity: O(N).
Approach 2: Randomized Guessing with Strategy	Time Complexity: O(N) for each guess where N is the length of words. Space Complexity: O(N) for maintaining words.

Complexity analysis

Approach	Time	Space	When to Use
Randomized Guessing with Filtering	O(n^2 * L) expected	O(n)	Quick implementation when constraints are small and worst-case guarantees are not critical
Minimax Strategy	O(n^2 * L)	O(n)	Interview-preferred solution that minimizes worst-case candidate set after each guess

Frequently asked questions

Is Guess the Word easy or hard?

Guess the Word is classified as a Hard problem on LeetCode. The difficulty comes from designing a strategy that consistently finds the secret within 10 guesses. Implementing the minimax partition logic and reasoning about worst-case reductions makes it significantly more complex than typical string problems.

How to solve Guess the Word efficiently?

Use a minimax-style selection strategy. For every candidate word, simulate how it partitions the remaining words by match count. Pick the word whose worst-case partition is smallest, then filter the candidate list using the feedback from the interactive guess. This ensures the search space shrinks quickly.

What is the best approach for Guess the Word?

The minimax strategy is the most reliable approach. For each possible guess, group the remaining candidate words by how many characters match. Choose the word that minimizes the largest group in the worst case. This keeps the candidate space shrinking efficiently and guarantees strong performance within the 10-guess limit.

What data structure is used in Guess the Word?

The solution mainly uses arrays or lists to maintain candidate words and frequency arrays to track match-count partitions. String comparison functions compute positional matches between two words. The overall strategy relies on filtering and grouping operations on these collections.

What is the time complexity of Guess the Word?

Most optimized solutions run in O(n^2 * L) time, where n is the number of candidate words and L is the word length (6). The algorithm compares pairs of words to calculate positional matches and repeatedly filters the candidate list after each guess. Space complexity is O(n) for storing remaining candidates.

Is Guess the Word asked at Google, Amazon, or Meta?

Guess the Word is commonly associated with Google-style interview problems because it combines interactive APIs, elimination strategies, and adversarial reasoning. Similar guessing and information-reduction problems appear in interviews at major tech companies including Google and Meta.

Is there a Python or Java solution for Guess the Word?

Solutions are commonly implemented in Python, Java, C++, and JavaScript. Each implementation follows the same pattern: compute match counts between words, select the next guess using either minimax or random strategy, and filter the remaining candidate list based on the interactive response.

Guess the Word solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Minimax Strategy

Approach 2: Approach 2: Randomized Guessing with Strategy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Guess the Word solution and explanation

The problem

Approach overview

Approach 1: Approach 1: Minimax Strategy

Approach 2: Approach 2: Randomized Guessing with Strategy

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems