Problem Summary

This is an interactive problem.
You are given a secret word chosen from a list of unique words.
Each word has exactly 6 lowercase letters.

You do not know which word is the secret word, but you can call:

int guess(String word)

This function returns the number of positions where the guessed word matches the secret word exactly.

Your objective is to identify the secret word in at most 10 guesses.

Constraints

• All words have length 6
• Word list contains up to a few hundred words
• All words are unique
• At most 10 calls to guess() are allowed
• The judge picks a secret from the given list

Because the number of guesses is limited, this is not a brute-force problem.

---

Approach

This problem is essentially a search game where the goal is to eliminate as many candidate words as possible after each guess.

A naive approach guesses randomly, but it often fails in the worst case.

The correct strategy must minimize the worst-case remaining words.

The well-known and accepted solution uses minimax selection (similar to Mastermind strategies).

Key Idea

For every possible guess word, try to determine how effectively it partitions the remaining candidate list.

Then choose the word that minimizes the size of the largest partition.
This guarantees maximum elimination in the worst case.

Why This Works

When you guess a word, the judge returns a number from 0 to 6 (number of matched positions).
This creates 7 possible groups of remaining candidates:

Group 0: words with 0 matches (to the guessed word)
Group 1: words with 1 match
...
Group 6: words with 6 matches

If we choose a guess poorly, one of these groups may still contain many words, and we may run out of guesses.

We therefore choose the guess that minimizes the size of the largest group, ensuring progress regardless of the judge’s response.

This is classical minimax: minimize the worst-case outcome.

Steps in Each Iteration

1. For each candidate word, compute how similar it is to every other candidate word.
2. For each word, compute the worst-case number of remaining words after guessing it.
3. Select the word with the smallest worst-case group size.
4. Make a guess using the provided API.
5. Filter the list to only those words that match the returned score.
6. Repeat until the secret is found.

Time complexity is manageable because the word list is fairly small.

---

Helper Function: Match Count

Two words match if they have the same character at a position.
We compute how many positions match:

private int matchCount(String a, String b) {
    int count = 0;
    for (int i = 0; i < 6; i++) {
        if (a.charAt(i) == b.charAt(i)) count++;
    }
    return count;
}

---

Java Code (Minimax Strategy)

class Solution {

    public void findSecretWord(String[] wordlist, Master master) {

        List<String> candidates = new ArrayList<>(Arrays.asList(wordlist));

        for (int attempt = 0; attempt < 10; attempt++) {

            // Choose the best word based on minimax criteria
            String guessWord = chooseWord(candidates);

            int matches = master.guess(guessWord);
            if (matches == 6) return;  // Found secret word

            // Reduce candidates to only those with same match count
            List<String> filtered = new ArrayList<>();
            for (String w : candidates) {
                if (matchCount(w, guessWord) == matches) {
                    filtered.add(w);
                }
            }
            candidates = filtered;
        }
    }

    private String chooseWord(List<String> candidates) {
        int bestScore = Integer.MAX_VALUE;
        String bestWord = candidates.get(0);

        for (String w1 : candidates) {
            int[] count = new int[7];  // match count from 0..6
            for (String w2 : candidates) {
                if (!w1.equals(w2)) {
                    int matches = matchCount(w1, w2);
                    count[matches]++;
                }
            }

            int worst = 0;
            for (int c : count) {
                if (c > worst) worst = c;
            }

            if (worst < bestScore) {
                bestScore = worst;
                bestWord = w1;
            }
        }
        return bestWord;
    }

    private int matchCount(String a, String b) {
        int count = 0;
        for (int i = 0; i < 6; i++) {
            if (a.charAt(i) == b.charAt(i)) count++;
        }
        return count;
    }
}

---

Dry Run (Conceptual)

Assume the wordlist:

["acckzz", "ccbazz", "eiowzz", "abcczz"]
Secret = "acckzz"

Step 1: First Guess

Candidates = all 4 words.

Minimax evaluates each word:

• If guess “acckzz”, worst-case remaining = small
• If guess “ccbazz”, worst-case remaining = larger
• etc.

Suppose minimax selects “acckzz”.

Call:

master.guess("acckzz") → returns 6

Since matches = 6, secret is found.

Step-by-step behavior for non-immediate matches

If the guess had returned, for example, 2 matches:

1. Compute match count of every candidate with the guessed word.
2. Keep only those that have exactly 2 matching positions.
3. Iterate again with minimax selection.

This reduces candidates dramatically each round.

---

Time and Space Complexity

Time Complexity:
O(n² * L), where n is number of words and L=6
Since L is constant, approx O(n²)

Space Complexity:
O(n) for storing candidate lists and arrays.