LeetCode Problem 843

Difficulty: 🔴 Hard
Topics: Array, Math, String, Interactive, Game Theory

Solution

LeetCode 843 - Guess the Word

Problem Understanding

This is an interactive problem where we must identify a hidden six-letter word from a given list of candidate words. We are not allowed to directly inspect the secret word. Instead, we can interact with the provided Master API by calling master.guess(word).

Each call returns the number of characters that match exactly in both value and position between our guessed word and the secret word. For example, if the secret is "acckzz" and we guess "abcczz", the return value is 4 because four positions contain the same character.

The important detail is that the guessed word must come from the provided words list. If we guess something outside the list, the API returns -1.

The goal is to discover the secret word within a limited number of guesses. The problem guarantees that a reasonable strategy can always succeed within the allowed number of guesses.

The input consists of:

• words, a list of unique six-character strings
• master, the interactive API
• a hidden secret word that is guaranteed to exist in words

The function itself does not return anything. Instead, success is determined by whether one of our guesses exactly equals the secret word within the allowed number of calls.

The constraints are relatively small:

• At most 100 words
• Each word has length 6
• At most 30 guesses allowed

These constraints are important because they suggest we can afford pairwise comparisons between words. Since the word length is fixed at 6 and the list size is at most 100, even an O(n^2) preprocessing strategy is completely practical.

Several edge cases are important:

• The candidate list may contain only one word
• Many words may be extremely similar
• A poor guessing strategy can eliminate very few candidates and exceed the guess limit
• We must never guess words outside the provided list
• The secret is guaranteed to exist, so filtering candidates based on match counts is always valid

Approaches

Brute Force Approach

A naive strategy would repeatedly guess words in arbitrary order, such as always choosing the first remaining candidate.

After each guess, we receive a match count. We then filter the remaining candidate list to keep only words that would produce the same match count relative to the guessed word.

This approach is correct because the secret must be consistent with all feedback received so far. Any word that disagrees with a previous match count cannot possibly be the secret.

However, this strategy performs poorly in practice because the guessed word may provide very little information. If the selected guess is not representative of the remaining candidates, the candidate pool shrinks slowly. In worst cases, we may exceed the allowed number of guesses.

Optimal Approach

The key insight is that every guess should maximize information gain.

Suppose we guess a word that is very similar to many other candidates. If the returned match count is not informative, we may still be left with a large candidate set.

Instead, we want to choose a guess that partitions the remaining candidates as evenly as possible.

A common and effective strategy is the minimax approach:

• For every possible guess, compute how many candidate words would remain for each possible match count
• The worst-case remaining group size represents the worst outcome for that guess
• Choose the guess whose worst-case group is as small as possible

This strategy aggressively reduces uncertainty and reliably converges within the guess limit.

Since the constraints are small, we can afford pairwise comparisons between all words.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(G × n²)	O(n)	Arbitrary guessing may eliminate candidates slowly
Optimal	O(G × n²)	O(n²)	Uses minimax-style candidate reduction

Here:

• n is the number of words
• G is the number of guesses
• Each comparison costs only O(6) because words have fixed length

Algorithm Walkthrough

Step 1: Define a match-count helper function

We need a function that compares two six-letter words and returns how many positions contain the same character.

For example:

• "acckzz" vs "abcczz" returns 4

This function is central because all filtering decisions depend on exact positional matches.

Step 2: Maintain a candidate list

Initially, every word in words could be the secret.

We store all current possibilities in a list called candidates.

Step 3: Select the best next guess

For every word in the current candidate list:

1. Compare it against every other candidate
2. Group candidates by match count
3. Track the size of the largest group

The largest group represents the worst-case number of remaining candidates if we choose that word.

We pick the word with the smallest worst-case group size.

This is the minimax principle, minimize the worst possible outcome.

Step 4: Make the guess

Call:

matches = master.guess(best_word)

If the result is 6, we found the secret word and can stop immediately.

Step 5: Filter candidates

Only words consistent with the feedback can remain possible.

A candidate survives if:

match(candidate, guessed_word) == matches

All inconsistent words are discarded.

Step 6: Repeat

Continue selecting optimal guesses and shrinking the candidate set until the secret is found.

Why it works

At every step, the candidate list contains exactly the words consistent with all previous feedback.

The minimax selection strategy guarantees that each guess reduces uncertainty as much as possible in the worst case. Since the candidate set continuously shrinks and the secret is guaranteed to exist in the original list, the algorithm eventually isolates the correct word.

Python Solution

from typing import List
from collections import defaultdict

# """
# 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:
    def findSecretWord(self, words: List[str], master: 'Master') -> None:
        
        def match_count(word1: str, word2: str) -> int:
            matches = 0
            for i in range(6):
                if word1[i] == word2[i]:
                    matches += 1
            return matches
        
        candidates = words[:]
        
        while candidates:
            best_word = None
            best_score = float('inf')
            
            # Choose the word with the smallest worst-case partition
            for word in candidates:
                groups = defaultdict(int)
                
                for other in candidates:
                    if word != other:
                        matches = match_count(word, other)
                        groups[matches] += 1
                
                worst_group = max(groups.values(), default=0)
                
                if worst_group < best_score:
                    best_score = worst_group
                    best_word = word
            
            matches = master.guess(best_word)
            
            if matches == 6:
                return
            
            next_candidates = []
            
            for word in candidates:
                if match_count(word, best_word) == matches:
                    next_candidates.append(word)
            
            candidates = next_candidates

The implementation begins with the match_count helper function. Since every word has fixed length 6, we simply compare characters position by position and count equal positions.

The candidates list tracks all words still consistent with previous guesses.

For each iteration, we search for the best next guess using the minimax strategy. We simulate the effect of guessing every candidate word by grouping remaining candidates according to their match counts. The largest group represents the worst-case scenario after that guess.

We select the word with the smallest worst-case group size because it provides the strongest guaranteed reduction in uncertainty.

After calling master.guess, we immediately stop if the match count is 6.

Otherwise, we rebuild the candidate list by keeping only words consistent with the returned feedback.

This process repeats until the secret is found.

Go Solution

package main

import "math"

/**
 * // This is the Master's API interface.
 * // You should not implement it, or speculate about its implementation
 * type Master struct {
 * }
 *
 * func (this *Master) Guess(word string) int {}
 */

func matchCount(word1 string, word2 string) int {
	count := 0

	for i := 0; i < 6; i++ {
		if word1[i] == word2[i] {
			count++
		}
	}

	return count
}

func findSecretWord(words []string, master *Master) {
	candidates := make([]string, len(words))
	copy(candidates, words)

	for len(candidates) > 0 {
		bestWord := ""
		bestScore := math.MaxInt32

		// Choose word with minimum worst-case partition size
		for _, word := range candidates {
			groups := make(map[int]int)

			for _, other := range candidates {
				if word != other {
					matches := matchCount(word, other)
					groups[matches]++
				}
			}

			worstGroup := 0

			for _, size := range groups {
				if size > worstGroup {
					worstGroup = size
				}
			}

			if worstGroup < bestScore {
				bestScore = worstGroup
				bestWord = word
			}
		}

		matches := master.Guess(bestWord)

		if matches == 6 {
			return
		}

		nextCandidates := []string{}

		for _, word := range candidates {
			if matchCount(word, bestWord) == matches {
				nextCandidates = append(nextCandidates, word)
			}
		}

		candidates = nextCandidates
	}
}

The Go implementation mirrors the Python solution closely.

The primary differences come from language syntax and container management:

• Go uses slices instead of Python lists
• We use a map[int]int to count partition sizes
• math.MaxInt32 initializes the best minimax score
• Slice rebuilding is explicit using append

There are no integer overflow concerns because all counts remain very small.

Worked Examples

Example 1

secret = "acckzz"
words = ["acckzz","ccbazz","eiowzz","abcczz"]

Initial candidates:

Candidates
acckzz
ccbazz
eiowzz
abcczz

Suppose the algorithm selects "abcczz" first.

We call:

master.guess("abcczz")

Result:

4

Now we filter candidates.

Word	Matches with "abcczz"	Keep?
acckzz	4	Yes
ccbazz	2	No
eiowzz	2	No
abcczz	6	No

Remaining candidates:

Candidates
acckzz

Next guess:

master.guess("acckzz")

Result:

6

We found the secret word.

Example 2

secret = "hamada"
words = ["hamada","khaled"]

Initial candidates:

Candidates
hamada
khaled

Suppose we guess "khaled".

master.guess("khaled")

Result:

2

Filter candidates:

Word	Matches with "khaled"	Keep?
hamada	2	Yes
khaled	6	No

Remaining candidate:

Candidates
hamada

Next guess:

master.guess("hamada")

Result:

6

Secret found.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(G × n²)	Each guess compares candidate pairs
Space	O(n²)	Pairwise grouping and candidate storage

The dominant work comes from evaluating every possible guess against every remaining candidate. Since n ≤ 100, this remains efficient in practice.

Each word comparison costs only constant time because all words have fixed length 6.

The number of guesses is bounded by the interactive limit, so overall runtime is easily acceptable.

Test Cases

def match_count(a, b):
    return sum(x == y for x, y in zip(a, b))

# Basic exact match
assert match_count("acckzz", "acckzz") == 6  # identical words

# Partial matches
assert match_count("acckzz", "abcczz") == 4  # mixed matching positions

# No matches
assert match_count("abcdef", "ghijkl") == 0  # completely different

# Single candidate
words = ["aaaaaa"]
assert words[0] == "aaaaaa"  # only one possible secret

# Two candidates
words = ["hamada", "khaled"]
assert len(words) == 2  # minimal non-trivial candidate set

# Highly similar words
words = [
    "aaaaaa",
    "aaaaba",
    "aaabaa",
    "aabaaa",
    "abaaaa",
]
assert len(words) == 5  # stresses filtering correctness

# Maximum length property
assert len("abcdef") == 6  # all words must be length 6

# Unique words guarantee
words = ["abcdef", "abcdeg", "abcdeh"]
assert len(words) == len(set(words))  # no duplicates

Test	Why
Identical words	Verifies full match counting
Partial matches	Ensures positional comparison correctness
Completely different words	Verifies zero-match handling
Single candidate	Tests smallest input size
Two candidates	Tests simple elimination
Highly similar words	Stresses filtering logic
Length-6 validation	Confirms constraint assumptions
Unique-word check	Verifies no duplicates

Edge Cases

Only One Candidate Word

If the input contains exactly one word, the algorithm should immediately guess it. A buggy implementation might attempt unnecessary partitioning logic or fail due to empty comparison groups.

This implementation handles the case naturally because the single word becomes the best candidate and is guessed immediately.

Extremely Similar Words

Many words may differ by only one or two positions. In such cases, poor guessing strategies eliminate very few candidates and can exceed the guess limit.

The minimax partition strategy specifically addresses this problem by selecting guesses that minimize the largest remaining ambiguity group.

Match Count of Zero

A guess may share no matching positions with the secret word. Incorrect filtering logic could accidentally retain inconsistent candidates.

The implementation correctly keeps only words whose computed match count exactly equals the API response, including zero. This guarantees consistency after every guess.