Problem Description

Alice and Bob are playing a word game with two lexicographically sorted arrays of strings, a and b, respectively.

The game follows these rules:

• Players take turns playing words from their respective arrays
• On each turn, a player must play a word that is closely greater than the previously played word
• If a player cannot play a valid word on their turn, they lose
• Alice starts the game by playing her lexicographically smallest word (first word in array a)

A word w is closely greater than word z if:

1. w is lexicographically greater than z (comes after z in dictionary order)
2. The first letter of w must either:
   • Be equal to the first letter of z, OR
   • Be exactly one letter after the first letter of z in the alphabet

For example:

• "care" is closely greater than "book" (first letters: c comes after b by 1)
• "care" is closely greater than "car" (same first letter c, and "care" > "car")
• "care" is NOT closely greater than "ant" (first letters: c is 2 letters after a)
• "care" is NOT closely greater than "cook" ("care" is not lexicographically greater than "cook")

The function should return true if Alice can win the game when both players play optimally, and false otherwise.

The solution simulates the game using indices to track each player's current position in their array. Variable k alternates between 0 (Alice's turn) and 1 (Bob's turn), starting with Bob since Alice already played the first word. The algorithm checks if the current player can play any remaining word from their array that satisfies the "closely greater" condition. If a valid word is found, it becomes the new reference word and the turn switches. If a player exhausts their array without finding a valid word while it's still their turn, they lose.

Intuition

The key insight is that both players play optimally, which means each player will always play the earliest valid word from their sorted array when it's their turn. Why? Because playing words early preserves more options for future turns - if you skip a valid word now, you might not be able to use it later when the requirements become stricter.

Since both arrays are already lexicographically sorted, we can use a greedy approach with two pointers. For each player, we maintain a pointer that moves through their array from start to end, checking each word to see if it can be played.

The "closely greater" constraint limits which words can follow the current word - the next word must start with either the same letter or the very next letter in the alphabet. This means we don't need complex backtracking or dynamic programming; we can simply scan forward through each player's remaining words until we find one that satisfies the constraint.

The simulation approach naturally emerges from this observation:

• Start with Alice playing her first word (smallest in her array)
• Alternate turns between Bob and Alice
• On each turn, scan the current player's remaining words (using their pointer) to find the first valid word
• If found, play it and switch turns; if not, keep scanning
• The game ends when one player runs out of valid words to play

The winner is determined by who runs out of valid moves first. If Bob exhausts all his words while it's his turn to play (meaning he has no valid move), Alice wins. Conversely, if Alice exhausts all her words while it's her turn, Bob wins.

This greedy simulation works because of the optimal play assumption - each player will always make the move that gives them the best chance to have future valid moves, which in this sorted scenario means playing the earliest valid word available.

Learn more about Greedy, Math and Two Pointers patterns.

Solution Approach

The implementation uses a simulation approach with pointer tracking for both players' arrays.

Variables Setup:

• i = 1: Alice's pointer, starting at index 1 (since she already played a[0])
• j = 0: Bob's pointer, starting at index 0 (he hasn't played yet)
• k = 1: Turn indicator (0 for Alice, 1 for Bob), starting with 1 since Alice already played
• w = a[0]: The current word in play, initialized with Alice's first word

Main Simulation Loop:

The algorithm runs an infinite loop that alternates between players based on k:

When it's Bob's turn (k = 1):

1. First check if j == len(b) - if Bob has exhausted all his words without finding a valid move, Alice wins (return True)
2. Check if b[j] is a valid move:
   • Condition 1: b[j][0] == w[0] and b[j] > w (same first letter AND lexicographically greater)
   • Condition 2: ord(b[j][0]) - ord(w[0]) == 1 (first letter is exactly one position ahead in alphabet)
3. If either condition is met:
   • Update w = b[j] (this becomes the new current word)
   • Toggle turn with k ^= 1 (XOR with 1 flips between 0 and 1)
4. Always increment j += 1 to move to the next word in Bob's array

When it's Alice's turn (k = 0):

1. First check if i == len(a) - if Alice has exhausted all her words without finding a valid move, Bob wins (return False)
2. Check if a[i] is a valid move using the same "closely greater" conditions:
   • Condition 1: a[i][0] == w[0] and a[i] > w
   • Condition 2: ord(a[i][0]) - ord(w[0]) == 1
3. If either condition is met:
   • Update w = a[i]
   • Toggle turn with k ^= 1
4. Always increment i += 1 to move to the next word in Alice's array

Key Implementation Details:

• The ord() function converts a character to its ASCII value, allowing us to check if letters are consecutive (e.g., ord('c') - ord('b') == 1)
• The XOR operation k ^= 1 efficiently toggles between 0 and 1 for turn switching
• The pointer increment happens regardless of whether a valid word was found, ensuring we scan through all possibilities
• The game termination conditions are checked at the beginning of each player's turn - if they've exhausted their array, their opponent wins

This greedy approach works because both arrays are sorted, and playing the earliest valid word is always optimal since it preserves the maximum number of future options.

Example Walkthrough

Let's trace through a small example to understand how the solution works.

Given:

• Alice's array a = ["apple", "berry", "cherry"]
• Bob's array b = ["banana", "carrot", "date"]

Step 1: Initial Setup

• Alice plays her first word: w = "apple"
• Set pointers: i = 1 (Alice's next word), j = 0 (Bob starts at beginning)
• Turn indicator: k = 1 (Bob's turn)

Step 2: Bob's Turn (k = 1)

• Check if Bob has exhausted his array: j = 0 < 3, so continue
• Check if b[0] = "banana" is closely greater than "apple":
  • First letters: 'b' and 'a'
  • Is 'b' == 'a'? No
  • Is ord('b') - ord('a') == 1? Yes! (98 - 97 = 1)
  • Is "banana" > "apple"? Yes
• Valid move found! Update w = "banana", toggle k = 0, increment j = 1

Step 3: Alice's Turn (k = 0)

• Check if Alice has exhausted her array: i = 1 < 3, so continue
• Check if a[1] = "berry" is closely greater than "banana":
  • First letters: both 'b'
  • Is 'b' == 'b'? Yes
  • Is "berry" > "banana"? Yes
• Valid move found! Update w = "berry", toggle k = 1, increment i = 2

Step 4: Bob's Turn (k = 1)

• Check if Bob has exhausted his array: j = 1 < 3, so continue
• Check if b[1] = "carrot" is closely greater than "berry":
  • First letters: 'c' and 'b'
  • Is 'c' == 'b'? No
  • Is ord('c') - ord('b') == 1? Yes! (99 - 98 = 1)
  • Is "carrot" > "berry"? Yes
• Valid move found! Update w = "carrot", toggle k = 0, increment j = 2

Step 5: Alice's Turn (k = 0)

• Check if Alice has exhausted her array: i = 2 < 3, so continue
• Check if a[2] = "cherry" is closely greater than "carrot":
  • First letters: both 'c'
  • Is 'c' == 'c'? Yes
  • Is "cherry" > "carrot"? Yes
• Valid move found! Update w = "cherry", toggle k = 1, increment i = 3

Step 6: Bob's Turn (k = 1)

• Check if Bob has exhausted his array: j = 2 < 3, so continue
• Check if b[2] = "date" is closely greater than "cherry":
  • First letters: 'd' and 'c'
  • Is 'd' == 'c'? No
  • Is ord('d') - ord('c') == 1? Yes! (100 - 99 = 1)
  • Is "date" > "cherry"? Yes
• Valid move found! Update w = "date", toggle k = 0, increment j = 3

Step 7: Alice's Turn (k = 0)

• Check if Alice has exhausted her array: i = 3 == 3, Alice has no more words!
• Since Alice cannot play on her turn, Bob wins
• Return False

The game flow was: "apple" → "banana" → "berry" → "carrot" → "cherry" → "date", and Alice ran out of valid moves first, so Bob wins.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m + n), where m is the length of array a and n is the length of array b.

The algorithm uses two pointers i and j to traverse through arrays a and b respectively. In each iteration of the while loop, either i or j is incremented by 1. The loop continues until either:

• j reaches the end of array b (Alice wins), or
• i reaches the end of array a (Bob wins)

Since each element in both arrays is visited at most once, and the pointers only move forward, the total number of iterations is bounded by m + n. Therefore, the time complexity is O(m + n).

Space Complexity: O(1)

The algorithm only uses a constant amount of extra space:

• Three integer variables: i, j, and k for indexing and turn tracking
• One string variable w to store the current word

These variables do not depend on the input size, so the space complexity is constant O(1).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Turn Tracking Logic

The most critical pitfall in this solution is the confusing turn tracking system. The code uses alice_turn = True to indicate whose turn it is, but the logic is inverted:

• When alice_turn = True, the code processes Bob's turn
• When alice_turn = False, the code processes Alice's turn

This is counterintuitive and can lead to bugs when modifying or debugging the code.

Solution: Rename the variable to accurately reflect its purpose, or fix the logic:

# Option 1: Rename variable to match actual behavior
is_bobs_turn = True  # Start with Bob since Alice already played

while True:
    if is_bobs_turn:
        # Bob's turn logic
        ...
    else:
        # Alice's turn logic
        ...

# Option 2: Fix the logic to match variable name
alice_turn = False  # False because Alice already played, now it's Bob's turn

while True:
    if not alice_turn:  # Bob's turn
        # Bob's turn logic
        ...
    else:  # Alice's turn
        # Alice's turn logic
        ...

2. Missing Validation for "Closely Greater" Condition

The code doesn't validate that when checking ord(b[bob_index][0]) - ord(current_word[0]) == 1, the word is also lexicographically greater. A word starting with the next letter might still be lexicographically smaller (e.g., "ba" is not greater than "bz" even though 'b' comes after 'a').

Solution: Add explicit lexicographic comparison:

if (b[bob_index][0] == current_word[0] and b[bob_index] > current_word) or \
   (ord(b[bob_index][0]) - ord(current_word[0]) == 1 and b[bob_index] > current_word):
    # Valid move

3. Inefficient Array Scanning

The code increments indices even when no valid word is found, potentially scanning through many invalid words repeatedly. This doesn't affect correctness but impacts performance.

Solution: Use binary search to find the next valid word more efficiently:

def find_next_valid_word(words, start_idx, current_word):
    # Binary search for the first word that is closely greater
    left, right = start_idx, len(words)
    result_idx = -1
  
    while left < right:
        mid = (left + right) // 2
        if is_closely_greater(words[mid], current_word):
            result_idx = mid
            right = mid  # Look for earlier valid word
        else:
            left = mid + 1
  
    return result_idx

4. Edge Case: Empty Arrays

The code assumes array a has at least one element (accessing a[0] directly). If either array is empty, the code will crash.

Solution: Add validation at the beginning:

if not a or not b:
    return False  # Or handle according to game rules