Guess the Word
Guess the Word is a hard arrays & hashing problem solved with the greedy pattern.
The best approach, optimal (minimax guess), runs in O(G · n²) time and O(n) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (guess the first remaining candidate) up.
Problem
You are given a list words of distinct six-letter lowercase words. One of them is the hidden secret. You cannot read it, but you may call a provided function guess(word) (in Java it is inherited from the Master class), which returns how many positions of word hold the same letter as secret, or -1 once you have used up your calls.
You may call guess at most allowedGuesses times. Only guess words from the list. Return the secret word: your answer is accepted only if it is the secret and you never went over the limit. A good strategy needs far fewer calls than trying words one by one.
Examples
Example 1
- Input
words = ["kettle","bottle","settle","little","rattle"], secret = "little", allowedGuesses = 10- Output
"little"- Why
- guess("kettle") returns 4 (both end in "ttle"), so only bottle, little and rattle, which also share exactly 4 positions with kettle, stay possible. One or two more calls find "little".
Example 2
- Input
words = ["planet","plates","palace","prince"], secret = "palace", allowedGuesses = 10- Output
"palace"- Why
- Each answer from guess() rules out the words that would have produced a different count, so the secret is found well within 10 calls.
Constraints
1 <= words.length <= 100words[i].length == 6, lowercase English letters, all distinct.secretis one of the words.10 <= allowedGuesses <= 30
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (guess the first remaining candidate) | O(G · n) | O(n) |
| Optimal (minimax guess) | O(G · n²) | O(n) |
1Brute force (guess the first remaining candidate)
O(G · n)Each of the G guesses filters the pool in O(n · 6).O(n)The candidate pool.Keep a pool of words that could still be the secret. Guess the first one; the reply k says the secret shares exactly k positions with it, so keep only the words that share exactly k positions with the guess. Repeat until a guess returns 6.
- candidates = all words.
- Take w = candidates[0] and call k = guess(w).
- If k == 6, return w.
- Keep only the words x with matches(x, w) == k (this also drops w itself).
- Repeat; return an empty string if the pool runs out.
class Solution extends Master {
public String findSecretWord(String[] words) {
List<String> candidates = new ArrayList<>(Arrays.asList(words));
while (!candidates.isEmpty()) {
String w = candidates.get(0);
int k = guess(w);
if (k == 6) return w;
List<String> next = new ArrayList<>();
for (String x : candidates) {
if (matches(x, w) == k) next.add(x);
}
candidates = next;
}
return "";
}
private int matches(String a, String b) {
int same = 0;
for (int i = 0; i < 6; i++) if (a.charAt(i) == b.charAt(i)) same++;
return same;
}
}class Solution:
def findSecretWord(self, words: List[str]) -> str:
def matches(a: str, b: str) -> int:
return sum(1 for x, y in zip(a, b) if x == y)
candidates = list(words)
while candidates:
w = candidates[0]
k = guess(w)
if k == 6:
return w
candidates = [x for x in candidates if matches(x, w) == k]
return ""class Solution {
public:
string findSecretWord(vector<string>& words) {
vector<string> candidates = words;
while (!candidates.empty()) {
string w = candidates[0];
int k = guess(w);
if (k == 6) return w;
vector<string> next;
for (const string& x : candidates) {
if (matches(x, w) == k) next.push_back(x);
}
candidates = next;
}
return "";
}
private:
int matches(const string& a, const string& b) {
int same = 0;
for (int i = 0; i < 6; i++) if (a[i] == b[i]) same++;
return same;
}
};function findSecretWord(words) {
const matches = (a, b) => {
let same = 0;
for (let i = 0; i < 6; i++) if (a[i] === b[i]) same++;
return same;
};
let candidates = [...words];
while (candidates.length > 0) {
const w = candidates[0];
const k = guess(w);
if (k === 6) return w;
candidates = candidates.filter((x) => matches(x, w) === k);
}
return "";
}2Optimal (minimax guess)
O(G · n²)Each of the G guesses compares every pair of candidates (6 letters each).O(n)The candidate pool and a 7-slot counter.Same filtering, but choose the guess carefully. For each remaining candidate, split the pool into 7 groups by how many positions each word shares with it. Whatever the reply is, the next pool is one of those groups, so guess the candidate whose largest group is smallest. That guarantees the fastest worst-case shrink among candidate guesses.
- candidates = all words.
- For each candidate w, count how many candidates fall into each match count 0..6 and record the largest count.
- Guess the w with the smallest largest count (first one on ties); return it if guess(w) == 6.
- Keep only the candidates sharing exactly guess(w) positions with w, and repeat.
class Solution extends Master {
public String findSecretWord(String[] words) {
List<String> candidates = new ArrayList<>(Arrays.asList(words));
while (!candidates.isEmpty()) {
String best = candidates.get(0);
int bestWorst = Integer.MAX_VALUE;
for (String w : candidates) {
int[] groups = new int[7];
for (String x : candidates) groups[matches(w, x)]++;
int worst = 0;
for (int g : groups) worst = Math.max(worst, g);
if (worst < bestWorst) {
bestWorst = worst;
best = w;
}
}
int k = guess(best);
if (k == 6) return best;
List<String> next = new ArrayList<>();
for (String x : candidates) {
if (matches(x, best) == k) next.add(x);
}
candidates = next;
}
return "";
}
private int matches(String a, String b) {
int same = 0;
for (int i = 0; i < 6; i++) if (a.charAt(i) == b.charAt(i)) same++;
return same;
}
}class Solution:
def findSecretWord(self, words: List[str]) -> str:
def matches(a: str, b: str) -> int:
return sum(1 for x, y in zip(a, b) if x == y)
candidates = list(words)
while candidates:
best, best_worst = candidates[0], float("inf")
for w in candidates:
groups = [0] * 7
for x in candidates:
groups[matches(w, x)] += 1
worst = max(groups)
if worst < best_worst:
best_worst, best = worst, w
k = guess(best)
if k == 6:
return best
candidates = [x for x in candidates if matches(x, best) == k]
return ""class Solution {
public:
string findSecretWord(vector<string>& words) {
vector<string> candidates = words;
while (!candidates.empty()) {
string best = candidates[0];
int bestWorst = INT_MAX;
for (const string& w : candidates) {
int groups[7] = {0};
for (const string& x : candidates) groups[matches(w, x)]++;
int worst = *max_element(groups, groups + 7);
if (worst < bestWorst) {
bestWorst = worst;
best = w;
}
}
int k = guess(best);
if (k == 6) return best;
vector<string> next;
for (const string& x : candidates) {
if (matches(x, best) == k) next.push_back(x);
}
candidates = next;
}
return "";
}
private:
int matches(const string& a, const string& b) {
int same = 0;
for (int i = 0; i < 6; i++) if (a[i] == b[i]) same++;
return same;
}
};function findSecretWord(words) {
const matches = (a, b) => {
let same = 0;
for (let i = 0; i < 6; i++) if (a[i] === b[i]) same++;
return same;
};
let candidates = [...words];
while (candidates.length > 0) {
let best = candidates[0], bestWorst = Infinity;
for (const w of candidates) {
const groups = new Array(7).fill(0);
for (const x of candidates) groups[matches(w, x)]++;
const worst = Math.max(...groups);
if (worst < bestWorst) {
bestWorst = worst;
best = w;
}
}
const k = guess(best);
if (k === 6) return best;
candidates = candidates.filter((x) => matches(x, best) === k);
}
return "";
}Edge cases to test
- A single word: one guess is enough
- Words that differ in only one position, so every wrong guess returns 5 and removes only itself
- Random words where most pairs share 0 letters
Hints
Hint 1
After guess(w) returns k, the secret must share exactly k positions with w. Every word that does not can be thrown away.
Hint 2
Always guessing a word that is still possible is already much better than guessing in list order.
Hint 3
To shrink the pool fastest, pick the candidate whose worst-case group (words sharing the same match count with it) is smallest.
FAQ
What is the best time complexity for Guess the Word?
Optimal (minimax guess) runs in O(G · n²) time and O(n) extra space. Each of the G guesses compares every pair of candidates (6 letters each).
Which pattern does Guess the Word use?
It is a arrays & hashing problem that uses the greedy pattern. Other problems with the same pattern: Integer to Roman, Jump Game II, Jump Game.
Is there a brute force solution for Guess the Word?
Yes. Brute force (guess the first remaining candidate) takes O(G · n) time and O(n) space. Keep a pool of words that could still be the secret.
Which edge cases should I test for Guess the Word?
A single word: one guess is enough; Words that differ in only one position, so every wrong guess returns 5 and removes only itself; Random words where most pairs share 0 letters.