The Wording Game solution and explanation
The problem
Alice and Bob each have a lexicographically sorted array of strings named a and b respectively.
They are playing a wording game with the following rules:
- On each turn, the current player should play a word from their list such that the new word is closely greater than the last played word; then it's the other player's turn.
- If a player can't play a word on their turn, they lose.
Alice starts the game by playing her lexicographically smallest word.
Given a and b, return true if Alice can win knowing that both players play their best, and false otherwise.
A word w is closely greater than a word z if the following conditions are met:
wis lexicographically greater thanz.- If
w1is the first letter ofwandz1is the first letter ofz,w1should either be equal toz1or be the letter afterz1in the alphabet. - For example, the word
"care"is closely greater than"book"and"car", but is not closely greater than"ant"or"cook".
A string s is lexicographically greater than a string t if in the first position where s and t differ, string s has a letter that appears later in the alphabet than the corresponding letter in t. If the first min(s.length, t.length) characters do not differ, then the longer string is the lexicographically greater one.
Example 1:
Input: a = ["avokado","dabar"], b = ["brazil"] Output: false Explanation: Alice must start the game by playing the word "avokado" since it's her smallest word, then Bob plays his only word, "brazil", which he can play because its first letter, 'b', is the letter after Alice's word's first letter, 'a'. Alice can't play a word since the first letter of the only word left is not equal to 'b' or the letter after 'b', 'c'. So, Alice loses, and the game ends.
Example 2:
Input: a = ["ananas","atlas","banana"], b = ["albatros","cikla","nogomet"] Output: true Explanation: Alice must start the game by playing the word "ananas". Bob can't play a word since the only word he has that starts with the letter 'a' or 'b' is "albatros", which is smaller than Alice's word. So Alice wins, and the game ends.
Example 3:
Input: a = ["hrvatska","zastava"], b = ["bijeli","galeb"] Output: true Explanation: Alice must start the game by playing the word "hrvatska". Bob can't play a word since the first letter of both of his words are smaller than the first letter of Alice's word, 'h'. So Alice wins, and the game ends.
Constraints:
1 <= a.length, b.length <= 105a[i]andb[i]consist only of lowercase English letters.aandbare lexicographically sorted.- All the words in
aandbcombined are distinct. - The sum of the lengths of all the words in
aandbcombined does not exceed106.
Approach overview
Problem Overview: Two players play a turn-based word game using two lists of strings. Each move must pick a word whose starting character is strictly greater than the starting character of the previously played word. Players can only use words from their own list and cannot reuse words. The goal is to determine which player wins assuming both play optimally.
Approach 1: Greedy Simulation with Two Pointers (O(n + m) time, O(1) space)
Treat the game as a deterministic simulation. Both word lists are processed from left to right using two pointers. Track the current minimum starting character required for the next move. On a player's turn, advance their pointer until a word with a valid starting character is found. If such a word exists, update the current character and switch turns; otherwise that player loses immediately. The greedy insight is that choosing the earliest valid word always maximizes future options because any larger starting letter only restricts the opponent less. Each pointer only moves forward, so the total work is linear.
Character comparisons drive the entire game state, so the logic effectively reduces to scanning the arrays and skipping invalid candidates. This keeps the implementation simple: check the first character with word[0], compare it against the current threshold, and update pointers accordingly. The alternating turns model the game theory aspect, while pointer advancement makes it an efficient two pointers pattern applied to string arrays.
Recommended for interviews: The greedy simulation with two pointers is the expected solution. A naive idea might attempt to explore all possible plays, but that quickly becomes exponential because each move branches into multiple possibilities. Demonstrating the greedy insight—that the earliest valid word is always optimal—shows strong reasoning about game constraints. The final implementation runs in O(n + m) time with constant extra space and is easy to implement during an interview.
Solution
We use k to record whose turn it is, where k=0 means it is Alice's turn, and k=1 means it is Bob's turn. We use i to record Alice's index, j to record Bob's index, and w to record the current word. Initially, we set i=1, j=0, and w=a[0].
We perform the following steps repeatedly:
If k=1, we check if j is equal to the length of b. If it is, then Alice wins and we return true. Otherwise, we check if the first letter of b[j] is equal to the first letter of w. If it is, we check if b[j] is greater than w, or if the first letter of b[j] is one greater than the first letter of w. If either of these conditions is true, then Bob can play the j-th word. We set w=b[j] and toggle k. Otherwise, Bob cannot play the j-th word, so we increment j.
If k=0, we check if i is equal to the length of a. If it is, then Bob wins and we return false. Otherwise, we check if the first letter of a[i] is equal to the first letter of w. If it is, we check if a[i] is greater than w, or if the first letter of a[i] is one greater than the first letter of w. If either of these conditions is true, then Alice can play the i-th word. We set w=a[i] and toggle k. Otherwise, Alice cannot play the i-th word, so we increment i.
The time complexity is O(m+n), where m and n are the lengths of arrays a and b, respectively. We only need to traverse the arrays once. The space complexity is O(1).
class Solution:
def canAliceWin(self, a: List[str], b: List[str]) -> bool:
i, j, k = 1, 0, 1
w = a[0]
while 1:
if k:
if j == len(b):
return True
if (b[j][0] == w[0] and b[j] > w) or ord(b[j][0]) - ord(w[0]) == 1:
w = b[j]
k ^= 1
j += 1
else:
if i == len(a):
return False
if (a[i][0] == w[0] and a[i] > w) or ord(a[i][0]) - ord(w[0]) == 1:
w = a[i]
k ^= 1
i += 1class Solution {
public boolean canAliceWin(String[] a, String[] b) {
int i = 1, j = 0;
boolean k = true;
String w = a[0];
while (true) {
if (k) {
if (j == b.length) {
return true;
}
if ((b[j].charAt(0) == w.charAt(0) && w.compareTo(b[j]) < 0)
|| b[j].charAt(0) - w.charAt(0) == 1) {
w = b[j];
k = !k;
}
++j;
} else {
if (i == a.length) {
return false;
}
if ((a[i].charAt(0) == w.charAt(0) && w.compareTo(a[i]) < 0)
|| a[i].charAt(0) - w.charAt(0) == 1) {
w = a[i];
k = !k;
}
++i;
}
}
}
}class Solution {
public:
bool canAliceWin(vector<string>& a, vector<string>& b) {
int i = 1, j = 0, k = 1;
string w = a[0];
while (1) {
if (k) {
if (j == b.size()) {
return true;
}
if ((b[j][0] == w[0] && w < b[j]) || b[j][0] - w[0] == 1) {
w = b[j];
k ^= 1;
}
++j;
} else {
if (i == a.size()) {
return false;
}
if ((a[i][0] == w[0] && w < a[i]) || a[i][0] - w[0] == 1) {
w = a[i];
k ^= 1;
}
++i;
}
}
}
};function canAliceWin(a: string[], b: string[]): boolean {
let [i, j, k] = [1, 0, 1];
let w = a[0];
while (1) {
if (k) {
if (j === b.length) {
return true;
}
if ((b[j][0] === w[0] && w < b[j]) || b[j].charCodeAt(0) - w.charCodeAt(0) === 1) {
w = b[j];
k ^= 1;
}
++j;
} else {
if (i === a.length) {
return false;
}
if ((a[i][0] === w[0] && w < a[i]) || a[i].charCodeAt(0) - w.charCodeAt(0) === 1) {
w = a[i];
k ^= 1;
}
++i;
}
}
}func canAliceWin(a []string, b []string) bool {
i, j, k := 1, 0, 1
w := a[0]
for {
if k&1 == 1 {
if j == len(b) {
return true
}
if (b[j][0] == w[0] && w < b[j]) || b[j][0]-w[0] == 1 {
w = b[j]
k ^= 1
}
j++
} else {
if i == len(a) {
return false
}
if (a[i][0] == w[0] && w < a[i]) || a[i][0]-w[0] == 1 {
w = a[i]
k ^= 1
}
i++
}
}
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Game Simulation (Brute Force) | Exponential | O(n + m) | Conceptual reasoning about all possible plays; not practical for real constraints |
| Greedy Simulation with Two Pointers | O(n + m) | O(1) | Optimal approach when word lists can be scanned sequentially |
Frequently asked questions
Is The Wording Game easy or hard?
LeetCode classifies The Wording Game as Hard because it requires recognizing the greedy property of the game. Once the insight is clear, the implementation itself is relatively short and runs in linear time using a simple simulation.
The Wording Game Python/Java solution
The implementation is straightforward in Python, Java, C++, Go, or TypeScript. Maintain two indices for the word lists, track the current starting character constraint, and alternate turns while advancing pointers until a valid word is found or a player cannot move.
How to solve The Wording Game in O(n)?
Use a two-pointer greedy simulation. Maintain a variable representing the smallest allowed starting character for the next move. On each turn, advance the player's pointer until a valid word is found. Because every word is checked at most once, the total complexity becomes linear in the combined length of both arrays.
What is the best approach for The Wording Game?
The optimal solution uses a greedy simulation with two pointers. Each player advances through their list to find the first word whose starting character is strictly greater than the previous move. Because each pointer only moves forward once, the algorithm runs in O(n + m) time and O(1) extra space.
Is The Wording Game asked at Google/Amazon/Meta?
Game simulation and greedy string problems like The Wording Game appear in interviews at large tech companies including Google, Amazon, and Meta. The key skill being tested is recognizing that optimal play reduces to a deterministic greedy choice rather than exploring all game states.
What data structure is used in The Wording Game?
The solution mainly uses arrays (or lists) of strings and two pointer indices to scan them. No advanced data structures are required. Character comparison on each word's first letter drives the greedy decision.
What is the time complexity of The Wording Game?
The optimal greedy simulation runs in O(n + m) time where n and m are the sizes of the two word lists. Each pointer moves forward at most once through its list. The space complexity is O(1) since the algorithm only tracks indices and the current character constraint.