Generated by Codex with GPT-5

Difficulty: HARD

Problem: Guess the Word

Problem gist

This is an interactive guessing problem. There is a hidden six-letter word inside the given list, and the only way to learn about it is to call master.guess(word). The API returns how many positions match the secret exactly. For example, if the guess and secret have the same letter in positions 0, 2, and 5, the response is 3.

The goal is not to return a value. The solution must keep calling master.guess until it guesses the secret, while staying under the allowed number of calls.

The important observation is that every guess gives a constraint. If guessing abcxyz returns 2, then the secret must be one of the remaining words that also have exactly two position matches with abcxyz. Every other word can be discarded.

Solution idea

The straightforward strategy is:

• Keep a list of candidate words that could still be the secret.
• Guess one word.
• Use the returned match count to filter candidates.
• Repeat until the match count is 6.

The tricky part is choosing a good next guess. A random candidate usually works on friendly tests, but it can waste guesses. A stronger interview answer uses a minimax choice: for each possible guess, group the current candidates by the result that guess would produce: 0 matches, 1 match, …, 6 matches. The worst bucket is the largest group that could remain after the guess. Choose the word whose worst bucket is as small as possible.

That choice is practical because it asks, “If this guess goes badly, how many candidates can still survive?” The best guess is the one with the smallest bad case. It may not be a formal proof that every possible input is solved in ten guesses, but it is the standard robust strategy for this LeetCode setup, where there are at most 100 words of fixed length 6.

How to derive it

Start from the API response. The response is only useful because exact-match count is symmetric: if the secret has k matches with the guess, then any valid remaining candidate must also have k matches with that same guess.

So after one guess, the candidate set becomes one compatibility bucket. The next question is how to make that bucket small. Since the solution does not know which bucket the secret will fall into, it scores a guess by the largest bucket it could leave behind. Minimizing that largest bucket gives the best local information gain.

This is the same instinct as binary search, but with seven possible outcomes instead of two. A good guess divides the candidates evenly across the seven match counts; a poor guess leaves most candidates in one bucket and teaches very little.

Python solution

from typing import Dict, List


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


class Solution:
    WORD_LENGTH = 6
    MAX_GUESSES = 10

    def findSecretWord(self, words: List[str], master: "Master") -> None:
        candidates = list(words)

        for _ in range(self.MAX_GUESSES):
            guess = self._choose_minimax_guess(candidates)
            exact_matches = master.guess(guess)

            if exact_matches == self.WORD_LENGTH:
                return

            candidates = self._filter_consistent_candidates(
                candidates,
                guess,
                exact_matches,
            )

    def _choose_minimax_guess(self, candidates: List[str]) -> str:
        best_guess = candidates[0]
        best_worst_bucket_size = len(candidates)

        for guess in candidates:
            bucket_sizes = self._count_result_buckets(guess, candidates)
            worst_bucket_size = max(bucket_sizes.values(), default=0)

            if worst_bucket_size < best_worst_bucket_size:
                best_guess = guess
                best_worst_bucket_size = worst_bucket_size

        return best_guess

    def _count_result_buckets(
        self,
        guess: str,
        candidates: List[str],
    ) -> Dict[int, int]:
        bucket_sizes: Dict[int, int] = {}

        for candidate in candidates:
            matches = self._count_exact_matches(guess, candidate)
            bucket_sizes[matches] = bucket_sizes.get(matches, 0) + 1

        return bucket_sizes

    def _filter_consistent_candidates(
        self,
        candidates: List[str],
        guess: str,
        exact_matches: int,
    ) -> List[str]:
        return [
            candidate
            for candidate in candidates
            if self._count_exact_matches(guess, candidate) == exact_matches
        ]

    def _count_exact_matches(self, first_word: str, second_word: str) -> int:
        return sum(
            first_char == second_char
            for first_char, second_char in zip(first_word, second_word)
        )

The loop runs at most 10 times. Each minimax choice compares each candidate guess against each current candidate, and each comparison checks 6 characters. With n words and fixed length L = 6, the time complexity is O(10 * n^2 * L), which is effectively O(n^2) for this problem. The extra space is O(n) for buckets and filtered candidates.

Interview follow-ups

Why is random guessing weaker?

Random guessing still uses the same filtering rule, so it is logically correct after each API response. The risk is that a random guess can split the candidate set poorly. If most candidates share the same match count with that guess, the response leaves almost the same problem for the next round.

The minimax version improves the expected behavior and the bad-case behavior by choosing a guess that minimizes the largest possible remaining group. It spends O(n^2) work locally to save scarce interactive calls, which is the right tradeoff when the API call budget is the real constraint.

Can the guess come from outside the current candidate set?

Yes, as long as it comes from the original word list. A word that is already known not to be the secret can still provide information because its match count partitions the remaining candidates.

The tradeoff is subtle. Guessing outside the candidate set can sometimes create a cleaner split, but it has no chance of immediately winning. Guessing inside the candidate set both partitions the search space and may hit the secret. For this problem size, choosing from the current candidates is simple, robust, and interview-friendly. A more exhaustive variant can score every original word and prefer candidate words only as a tie-breaker.

How would this change if words had variable length?

The exact-match function needs both words to be comparable position by position. If all candidate words still have the same length, the same minimax strategy works and WORD_LENGTH becomes len(words[0]).

If lengths can differ and the API still returns positional matches only up to some definition, the solution must first mirror that exact API definition. The filtering rule remains the same: keep only candidates that would have produced the observed response for the guess. Complexity becomes O(guesses * n^2 * L), where L is the comparison cost for two words.

What if the allowed guess count is much larger?

With more guesses, the simpler random or arbitrary-candidate filtering strategy becomes more acceptable because there is more room for inefficient splits. Minimax is still safe, but the extra O(n^2) scoring work may be unnecessary.

In an interview, the right answer depends on which resource is scarce. If API calls are expensive or limited, use minimax. If local CPU is the bottleneck and many guesses are allowed, pick any candidate, filter consistently, and keep the implementation smaller.

How can the minimax scoring be optimized?

The match count between any two words never changes, so the solution can precompute a matrix where matches[i][j] stores the exact-match count for words[i] and words[j]. Then filtering and bucket scoring use table lookups instead of repeatedly comparing characters.

This does not change the asymptotic O(n^2) scoring shape, but it reduces constant factors and makes each interactive round faster. The tradeoff is O(n^2) extra memory, which is fine for n <= 100 but less attractive if the word list is much larger.