Watch 10 video solutions for The Wording Game, a hard level problem involving Array, Math, Two Pointers. This walkthrough by Ashish Pratap Singh has 1,002,273 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
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:
w is lexicographically greater than z.w1 is the first letter of w and z1 is the first letter of z, w1 should either be equal to z1 or be the letter after z1 in the alphabet."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] and b[i] consist only of lowercase English letters.a and b are lexicographically sorted.a and b combined are distinct.a and b combined does not exceed 106.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.
| 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 |