LeetCode 2868 - The Wording Game

Difficulty: 🔴 Hard
Topics: Array, Math, Two Pointers, String, Greedy, Game Theory

Solution

Problem Understanding

The problem describes a turn-based game between Alice and Bob, where both players have a lexicographically sorted list of words. Alice always starts by playing her lexicographically smallest word, and the players then alternate turns. On each turn, the current player must select a word from their list that is closely greater than the previously played word. A word w is closely greater than z if it satisfies two conditions: it is lexicographically greater than z, and its first letter is either the same as z or the next letter in the alphabet. If a player cannot play a valid word, they lose immediately.

The inputs are two lists of strings, a for Alice and b for Bob, both lexicographically sorted, and all words across both lists are distinct. The goal is to determine if Alice can force a win assuming both players play optimally.

Constraints provide important insights into the problem scale. With 1 <= a.length, b.length <= 10^5 and total characters across all words ≤ 10^6, any brute-force recursion exploring all possible word sequences is infeasible. Efficient traversal or greedy strategies must rely on the lexicographical sorting and first-letter constraints. Edge cases include situations where one player's smallest word immediately blocks the opponent or where all words start with letters that do not allow a valid move.

Approaches

Brute Force

The naive approach is to simulate every possible sequence of moves recursively. For each move, we would generate all valid next words for the opponent and recurse. This guarantees correctness because it explores every possible game path, but it is too slow. With lists up to 10^5 words, exploring all paths leads to exponential time complexity, O(2^(n+m)), which is unacceptable.

Optimal Approach

The key observation is that the game’s constraints and lexicographical sorting allow a greedy, one-pass simulation using two pointers. Since the words are sorted, we can track the smallest valid word the current player can play given the last word. The first-letter restriction further restricts which words are playable.

The optimal approach is:

Start with Alice's smallest word as the initial last-played word.
Using two pointers for Alice and Bob, find the smallest word in each player's list that is closely greater than the last word.
Alternate turns and update the last-played word. If at any turn a player has no valid word, they lose immediately.

This approach is efficient because we only move forward through each sorted list once, achieving linear time relative to the total number of words.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^(n+m))	O(n+m)	Recursively explore all sequences; infeasible for large lists
Optimal	O(n + m)	O(1)	Two-pointer simulation leveraging sorting and first-letter constraints

Algorithm Walkthrough

Initialize pointers i = 0 for Alice and j = 0 for Bob. Set last_word to Alice’s lexicographically smallest word (a[0]), and increment Alice’s pointer i.
Set a flag alice_turn = False to indicate Bob's turn next.
Repeat until a player loses:
If it is Alice’s turn, iterate pointer i until a[i] is closely greater than last_word. If no such word exists, Alice loses and return False. Otherwise, update last_word to a[i] and increment i.
If it is Bob’s turn, iterate pointer j until b[j] is closely greater than last_word. If no such word exists, Alice wins and return True. Otherwise, update last_word to b[j] and increment j.
Alternate turns (alice_turn = not alice_turn).
The game ends as soon as a player cannot make a valid move, returning the correct outcome.

Why it works: The lexicographical sorting ensures that the first word found using the pointer is the smallest valid move, which is optimal in a turn-based game. Because both players play optimally and we always choose the smallest valid word, the simulation correctly determines whether Alice can force a win.

Python Solution

from typing import List

class Solution:
    def canAliceWin(self, a: List[str], b: List[str]) -> bool:
        def is_closely_greater(w: str, z: str) -> bool:
            if w <= z:
                return False
            return ord(w[0]) == ord(z[0]) or ord(w[0]) == ord(z[0]) + 1

        i, j = 1, 0  # Alice starts with her first word
        last_word = a[0]
        alice_turn = False  # Next turn is Bob's

        while True:
            if alice_turn:
                while i < len(a) and not is_closely_greater(a[i], last_word):
                    i += 1
                if i == len(a):
                    return False
                last_word = a[i]
                i += 1
            else:
                while j < len(b) and not is_closely_greater(b[j], last_word):
                    j += 1
                if j == len(b):
                    return True
                last_word = b[j]
                j += 1
            alice_turn = not alice_turn

The Python implementation defines a helper function is_closely_greater to enforce the game rules. Two pointers iterate through Alice and Bob's lists, moving only forward to find the next valid move. The game alternates turns until a player cannot move, returning the correct winner.

Go Solution

func canAliceWin(a []string, b []string) bool {
    isCloselyGreater := func(w, z string) bool {
        if w <= z {
            return false
        }
        return w[0] == z[0] || w[0] == z[0]+1
    }

    i, j := 1, 0
    lastWord := a[0]
    aliceTurn := false

    for {
        if aliceTurn {
            for i < len(a) && !isCloselyGreater(a[i], lastWord) {
                i++
            }
            if i == len(a) {
                return false
            }
            lastWord = a[i]
            i++
        } else {
            for j < len(b) && !isCloselyGreater(b[j], lastWord) {
                j++
            }
            if j == len(b) {
                return true
            }
            lastWord = b[j]
            j++
        }
        aliceTurn = !aliceTurn
    }
}

In Go, the implementation mirrors Python with type-safe string handling. Slice indices and ASCII comparisons ensure correct evaluation of the first-letter rule.

Worked Examples

Example 1

Turn	Player	Word Played	Last Word	Notes
1	Alice	"avokado"	"avokado"	Smallest word starts the game
2	Bob	"brazil"	"brazil"	First letter 'b' is next after 'a'
3	Alice	N/A	N/A	No word starting with 'b' or 'c' left; Alice loses

Result: False

Example 2

Turn	Player	Word Played	Last Word	Notes
1	Alice	"ananas"	"ananas"	Starts the game
2	Bob	N/A	"ananas"	No valid word greater than "ananas"; Alice wins

Result: True

Example 3

Turn	Player	Word Played	Last Word	Notes
1	Alice	"hrvatska"	"hrvatska"	Starts the game
2	Bob	N/A	"hrvatska"	First letters of Bob's words are smaller; Alice wins

Result: True

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + m)	Each word is considered at most once using two pointers
Space	O(1)	Only a few variables and indices are stored; no extra space proportional to input

The linear time arises from iterating over each list exactly once. No recursion or additional data structures are used, ensuring constant space complexity.

Test Cases

solution = Solution()

# Provided examples
assert solution.canAliceWin(["avokado","dabar"], ["brazil"]) == False  # Alice loses
assert solution.canAliceWin(["ananas","atlas","banana"], ["albatros","cikla","nogomet"]) == True  # Alice wins
assert solution.canAliceWin(["hrvatska","zastava"], ["bijeli","galeb"]) == True  # Alice wins

# Edge cases
assert solution.canAliceWin(["a"], ["b"]) == False  # Only Bob can respond to 'a', Alice loses
assert solution.canAliceWin(["a","b","c"], ["d","e"]) == True  # Alice wins by exhausting Bob
assert solution.canAliceWin(["apple"], ["apple"]) == False  # Same starting word, Alice loses
assert