Guess the Word

HardInteractive · Candidate Filtering · Minimax🧩 String Manipulation LeetCode #843 ↗Updated Oct 30, 2026

Problem

A secret word was picked from words (distinct, each exactly 6 lowercase letters). Calling master.guess(w) returns -1 if w is not in the list, otherwise the number of positions where w and the secret hold the same letter. Implement findSecretWord(words, master) so that the secret itself is guessed within allowedGuesses calls.

Inputsecret = "bakery", words = ["banana","basket","bakery","rocket"]Outputsecret guessed within the limit

Inputguess("basket") when secret = "bakery"Output2 (b, a match)

Inputguess("zzzzzz")Output-1 (not in words)

1 ≤ words.length ≤ 100 · words[i].length == 6 · all words distinct · secret ∈ words · 10 ≤ allowedGuesses ≤ 30

Try it yourself

Java

class Solution {
    public void findSecretWord(String[] words, Master master) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Every answer m tells you the secret is among the words that match your guess in exactly m positions. Choose the guess whose largest such group is smallest (minimax), so even the worst reply shrinks the candidates a lot.

PatternString Manipulation

Instinct Reading, comparing or rebuilding text character by character? Walk indices on a char[] and build output with a StringBuilder, never with + in a loop.

Memory hack Chars in an array, pointers on the ends, builder at the back - strings are just arrays wearing a costume.

Open the String Manipulation guide →

Approaches

Brute ForceGuess Every Word in Order

Time O(n · L)Space O(1)

The secret is somewhere in the list, so calling guess on each word in turn must hit it. The return value is used only to stop when it equals 6.

Java

public void findSecretWord(String[] words, Master master) {
    for (String w : words) {
        if (master.guess(w) == 6) return; // found it
    }
}

Always finds the secret, but may need up to 100 guesses — far over the limit.

BetterGuess a Candidate, Keep Only Consistent Words

Time O(g · n · L)Space O(n)

After guessing w and hearing m, any word that does not share exactly m positions with w cannot be the secret, so drop it. Repeating with the first surviving candidate usually collapses the list in a few rounds (g = guesses made).

Java

public void findSecretWord(String[] words, Master master) {
    List<String> cand = new ArrayList<>(Arrays.asList(words));
    while (!cand.isEmpty()) {
        String g = cand.get(0);
        int m = master.guess(g);
        if (m == 6) return;
        List<String> next = new ArrayList<>();
        for (String w : cand) {
            if (matches(g, w) == m) next.add(w); // still consistent with the reply
        }
        cand = next;
    }
}
private int matches(String a, String b) {
    int m = 0;
    for (int i = 0; i < a.length(); i++) if (a.charAt(i) == b.charAt(i)) m++;
    return m;
}

Big improvement, but a bad first pick (reply 0) can leave most words alive.

OptimalMinimax Guess over a Precomputed Match Matrix

Time O(n² · (L + g))Space O(n²)

Precompute sim[i][j] = matching positions of words i and j. Each round, for every candidate count how the other candidates split by reply value 0..5; guess the one whose biggest group is smallest, then keep only the group matching the real reply. The guaranteed shrinkage keeps rounds low.

Java

public void findSecretWord(String[] words, Master master) {
    int n = words.length;
    int[][] sim = new int[n][n];
    for (int i = 0; i < n; i++)
        for (int j = i; j < n; j++) sim[i][j] = sim[j][i] = matches(words[i], words[j]);
    List<Integer> cand = new ArrayList<>();
    for (int i = 0; i < n; i++) cand.add(i);
    while (!cand.isEmpty()) {
        int pick = cand.get(0), bestWorst = Integer.MAX_VALUE;
        for (int g : cand) {
            int[] groups = new int[7];
            for (int c : cand) groups[sim[g][c]]++;
            int worst = 0; // group 6 is g itself, i.e. solved, so skip it
            for (int k = 0; k < 6; k++) worst = Math.max(worst, groups[k]);
            if (worst < bestWorst) { bestWorst = worst; pick = g; }
        }
        int m = master.guess(words[pick]);
        if (m == 6) return;
        List<Integer> next = new ArrayList<>();
        for (int c : cand) if (sim[pick][c] == m) next.add(c);
        cand = next;
    }
}
private int matches(String a, String b) {
    int m = 0;
    for (int i = 0; i < a.length(); i++) if (a.charAt(i) == b.charAt(i)) m++;
    return m;
}

Worst-case-aware choice that fits the 10-guess budget on realistic word lists.

Pro tip

Restrict guesses to current candidates — a guess that cannot be the secret never ends the game early.

At a glance

Level	Approach	Time	Space
Brute Force	Guess Every Word in Order	`O(n · L)`	`O(1)`
Better	Guess a Candidate, Keep Only Consistent Words	`O(g · n · L)`	`O(n)`
Optimal	Minimax Guess over a Precomputed Match Matrix	`O(n² · (L + g))`	`O(n²)`

Common pitfalls

Treating the reply as “common letters” — it counts same positions only.
Keeping words that match at least m positions instead of exactly m.
Guessing a word twice or a word outside the list — wastes a call.

Interview tips

Explain the elimination rule first; the guess-selection strategy is the follow-up.
Justify minimax: you optimise the worst reply because the secret is adversarial.
Mention the cheap alternative heuristic: pick the word sharing fewest 0-match partners.

Pattern

Minimax candidate elimination → interactive guessing where each reply partitions the remaining possibilities.

My notes saved in this browser