Hangman Optimal Strategy

Problem

Two players face off in a game of Hangman. Player 2 secretly picks a word from a known list. Player 1, the guesser, does not know which word was chosen. On each turn, Player 1 guesses a single letter. Player 2 must reveal every occurrence of that letter in the secret word (if any), or declare the letter a miss. The guesser’s goal is to identify the secret word while incurring as few misses as possible.

Both players act optimally: Player 2 selects a word that forces the worst-case number of misses, and Player 1 chooses letters to minimize that worst-case count. Design an algorithm that, given the list of candidate words, returns the sequence of letter guesses Player 1 should make to guarantee the minimum possible number of incorrect guesses.

Input

• word_list: List[str] – a non‑empty list of candidate words. All words have the same length and consist only of lowercase English letters.

Output

• List[str] – the ordered sequence of letters that Player 1 should guess, following an optimal strategy. The sequence must minimize the maximum number of misses across all possible secret words.

Constraints

• 1 <= len(word_list) <= 2000
• 1 <= word_length <= 20
• Words contain only characters 'a'–'z'.
• A letter may be guessed at most once; the guesser never repeats a letter.

Examples

Example 1

Input:  word_list = ['apple', 'apply', 'angle']
Output: ['p', 'e']

Explanation:

• Guess 'p': present in 'apple' and 'apply', but absent from 'angle'. If it is a miss, the secret word is identified as 'angle'.
• If 'p' is present, guess 'e': present in 'apple' and absent from 'apply'. Thus the word is identified with at most 1 miss.
• Zero misses are impossible because distinguishing the words requires guessing a letter absent from at least one candidate.

Example 2

Input:  word_list = ['cat', 'bat', 'rat']
Output: ['a', 't', 'c', 'b']

Explanation:

• Guess 'a': present in all words → 0 misses. Board: _ a _.
• Guess 't': present in all words → 0 misses. Board: _ a t.
• Guess 'c': present only in 'cat'. If the secret is 'cat', the word is identified; otherwise, this is one miss and the remaining possibilities are 'bat' and 'rat'.
• Guess 'b': if present, the word is 'bat'; if absent, this is a second miss and the word must be 'rat'. Thus at most 2 misses are needed, which is optimal.