Guess the Word

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

Examples

Example 1

1
2
3
4
5
6
7
8
9


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

1
2
3


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

Solution

Method 1 – Minimax with Match Counting

Intuition

To efficiently guess the secret word, we want to minimize the worst-case number of remaining candidates after each guess. For each guess, we can count how many words would remain for each possible match count, and pick the guess that minimizes the largest group. This is a minimax strategy. After each guess, we filter the word list to only those with the same number of matches as the guess result.

Approach

For up to allowedGuesses times:
- For each word in the current list, for each other word, count the number of matches at each position.
- For each word, record the largest group size of words with the same match count.
- Pick the word with the smallest largest group size as the next guess.
- Call Master.guess(word) and get the number of matches.
- If the guess is correct (6 matches), stop.
- Otherwise, filter the word list to only those with the same number of matches as the guess result.
Repeat until the secret is found or guesses run out.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution {
public:
    void findSecretWord(vector<string>& words, Master& master) {
        int n = words.size();
        for (int t = 0; t < 10; ++t) {
            vector<vector<int>> count(n, vector<int>(n));
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < n; ++j) {
                    int matches = 0;
                    for (int k = 0; k < 6; ++k) {
                        if (words[i][k] == words[j][k]) matches++;
                    }
                    count[i][j] = matches;
                }
            }
            int min_max = n, guess_idx = 0;
            for (int i = 0; i < n; ++i) {
                vector<int> groups(7);
                for (int j = 0; j < n; ++j) if (i != j) groups[count[i][j]]++;
                int max_group = *max_element(groups.begin(), groups.end());
                if (max_group < min_max) {
                    min_max = max_group;
                    guess_idx = i;
                }
            }
            string guess = words[guess_idx];
            int matches = master.guess(guess);
            if (matches == 6) return;
            vector<string> next;
            for (auto& w : words) {
                int m = 0;
                for (int k = 0; k < 6; ++k) if (w[k] == guess[k]) m++;
                if (m == matches) next.push_back(w);
            }
            words = next;
        }
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


class Solution:
    def findSecretWord(self, words: list[str], master: 'Master') -> None:
        from collections import Counter
        for _ in range(10):
            count = [[sum(a == b for a, b in zip(w1, w2)) for w2 in words] for w1 in words]
            min_max, guess_idx = float('inf'), 0
            for i, row in enumerate(count):
                groups = Counter(row)
                max_group = max(groups[j] for j in range(7) if j != 6)
                if max_group < min_max:
                    min_max = max_group
                    guess_idx = i
            guess = words[guess_idx]
            matches = master.guess(guess)
            if matches == 6:
                return
            words = [w for w in words if sum(a == b for a, b in zip(w, guess)) == matches]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38


class Solution {
    public void findSecretWord(String[] words, Master master) {
        int n = words.length;
        for (int t = 0; t < 10; t++) {
            int[][] count = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    int matches = 0;
                    for (int k = 0; k < 6; k++) {
                        if (words[i].charAt(k) == words[j].charAt(k)) matches++;
                    }
                    count[i][j] = matches;
                }
            }
            int minMax = n, guessIdx = 0;
            for (int i = 0; i < n; i++) {
                int[] groups = new int[7];
                for (int j = 0; j < n; j++) if (i != j) groups[count[i][j]]++;
                int maxGroup = 0;
                for (int g = 0; g < 6; g++) maxGroup = Math.max(maxGroup, groups[g]);
                if (maxGroup < minMax) {
                    minMax = maxGroup;
                    guessIdx = i;
                }
            }
            String guess = words[guessIdx];
            int matches = master.guess(guess);
            if (matches == 6) return;
            List<String> next = new ArrayList<>();
            for (String w : words) {
                int m = 0;
                for (int k = 0; k < 6; k++) if (w.charAt(k) == guess.charAt(k)) m++;
                if (m == matches) next.add(w);
            }
            words = next.toArray(new String[0]);
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    fun findSecretWord(words: Array<String>, master: Master) {
        var ws = words.toList()
        repeat(10) {
            val count = ws.map { w1 -> ws.map { w2 -> w1.zip(w2).count { it.first == it.second } } }
            var minMax = Int.MAX_VALUE
            var guessIdx = 0
            for ((i, row) in count.withIndex()) {
                val groups = IntArray(7)
                for (j in row.indices) if (i != j) groups[row[j]]++
                val maxGroup = groups.take(6).maxOrNull() ?: 0
                if (maxGroup < minMax) {
                    minMax = maxGroup
                    guessIdx = i
                }
            }
            val guess = ws[guessIdx]
            val matches = master.guess(guess)
            if (matches == 6) return
            ws = ws.filter { w -> w.zip(guess).count { it.first == it.second } == matches }
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


impl Solution {
    pub fn find_secret_word(words: Vec<String>, master: &mut Master) {
        let mut ws = words;
        for _ in 0..10 {
            let n = ws.len();
            let mut count = vec![vec![0; n]; n];
            for i in 0..n {
                for j in 0..n {
                    count[i][j] = ws[i].chars().zip(ws[j].chars()).filter(|(a, b)| a == b).count();
                }
            }
            let mut min_max = n;
            let mut guess_idx = 0;
            for i in 0..n {
                let mut groups = vec![0; 7];
                for j in 0..n {
                    if i != j { groups[count[i][j]] += 1; }
                }
                let max_group = *groups.iter().take(6).max().unwrap();
                if max_group < min_max {
                    min_max = max_group;
                    guess_idx = i;
                }
            }
            let guess = &ws[guess_idx];
            let matches = master.guess(guess.clone());
            if matches == 6 { return; }
            ws = ws.into_iter().filter(|w| w.chars().zip(guess.chars()).filter(|(a, b)| a == b).count() == matches).collect();
        }
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution {
    findSecretWord(words: string[], master: Master): void {
        for (let t = 0; t < 10; t++) {
            const n = words.length;
            const count: number[][] = Array.from({length: n}, () => Array(n).fill(0));
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    let matches = 0;
                    for (let k = 0; k < 6; k++) {
                        if (words[i][k] === words[j][k]) matches++;
                    }
                    count[i][j] = matches;
                }
            }
            let minMax = n, guessIdx = 0;
            for (let i = 0; i < n; i++) {
                const groups = Array(7).fill(0);
                for (let j = 0; j < n; j++) if (i !== j) groups[count[i][j]]++;
                const maxGroup = Math.max(...groups.slice(0, 6));
                if (maxGroup < minMax) {
                    minMax = maxGroup;
                    guessIdx = i;
                }
            }
            const guess = words[guessIdx];
            const matches = master.guess(guess);
            if (matches === 6) return;
            words = words.filter(w => w.split('').filter((c, k) => c === guess[k]).length === matches);
        }
    }
}

Complexity

⏰ Time complexity: O(n^2 * k) — For each guess, we compare all pairs of words of length k=6.
🧺 Space complexity: O(n^2) — For the match count matrix.

Problem#

Examples#

Example 1#

Example 2#

Constraints#

Solution#

Method 1 – Minimax with Match Counting#

Intuition#

Approach#

Code#

Complexity#