You are helping a player choose the next word in a word-matching game. The game has selected an unknown target from a list of playable words.

After every attempt, the player receives a score equal to the number of characters that match the target in both value and position.

Using the previous attempts and their scores, select the next word that minimizes the greatest number of possible targets that could remain.

Class

WordMatchStrategy

Method

selectNextWord

String selectNextWord( List<String> playableWords, List<String> previousAttempts, List<Integer> receivedScores )

Parameters

• playableWords: All words that could have been selected as the target. Each word in this list is unique.
• previousAttempts: The words previously attempted by the player.
• receivedScores: The score received for each corresponding previous attempt.

Returns

Return the best remaining word to attempt next.

If multiple words are equally good, return the lexicographically smallest one.

Matching Score

The matching score between two words is the number of positions containing the same character in both words.

For example, the matching score between "market" and "carpet" is 4.

Finding Possible Targets

A playable word remains a possible target only if it is consistent with every previous result.

For every valid index i, the matching score between that word and previousAttempts[i] must equal receivedScores[i].

Choosing the Next Word

Consider every remaining possible target as a possible next attempt.

For each possible attempt, group the remaining targets according to the matching score they would produce. A score may be any value from 0 to 6.

The risk of an attempt is the size of its largest score group. This is the greatest number of possible targets that might remain after receiving the next score.

Return the word with the smallest risk. If several words have the same smallest risk, return the lexicographically smallest word.

Rules

• Every word contains exactly six characters.
• Character positions are indexed from 0 to 5.
• If there are no previous attempts, every playable word is initially a possible target.
• If only one possible target remains, return that word.
• Previous scores are always less than 6 because the method is called only while the target has not been found.
• The given game history always leaves at least one possible target.

Constraints

• 1 ≤ playableWords.size() ≤ 100
• playableWords[i].length() == 6
• Every word contains only lowercase English letters.
• All words in playableWords are unique.
• 0 ≤ previousAttempts.size() ≤ min(30, playableWords.size() - 1)
• previousAttempts.size() == receivedScores.size()
• Every word in previousAttempts belongs to playableWords.
• All words in previousAttempts are unique.
• 0 ≤ receivedScores[i] ≤ 5

Example 1

selectNextWord( playableWords = ["market", "carpet", "basket", "rocket", "marble"], previousAttempts = ["market"], receivedScores = [4] )

Output: "basket"

Explanation

The words "carpet" and "basket" each have a matching score of 4 with "market". They are the only remaining possible targets.

Attempting either word separates the two targets into different score groups, giving both words a risk of 1. "basket" is returned because it is lexicographically smaller than "carpet".

Example 2

selectNextWord( playableWords = ["stream", "bright", "flight", "planet", "friend"], previousAttempts = [], receivedScores = [] )

Output: "bright"

Explanation

Since there are no previous attempts, all five words are possible targets.

The matching scores produced by attempting "bright" against the listed targets are 0, 6, 4, 1, and 2.

Every target belongs to a different score group, so the risk of "bright" is 1. This is the smallest possible risk.

Example 3

selectNextWord( playableWords = ["garden", "forest", "market", "pocket", "silver", "winter"], previousAttempts = ["forest", "silver"], receivedScores = [0, 3] )

Output: "winter"

Explanation

"winter" is the only playable word having a score of 0 with "forest" and a score of 3 with "silver". It is therefore the only possible target.