We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

The Wording Game

Number: 3173

Difficulty: Hard

Paid? Yes

Companies: N/A

Problem Description

Alice and Bob are playing a turn‐based “wording game.” Each has a lexicographically sorted array of unique strings (Alice’s array a and Bob’s array b). The game starts with Alice playing her lexicographically smallest word. On each subsequent turn the current player must choose (among the words not yet played from their own list) a word which is “closely greater” than the last played word. A word w is closely greater than the previous word z if (1) w is lexicographically greater than z, and (2) if z’s first letter is L then w’s first letter must be either L or the letter immediately following L (if L isn’t ‘z’). If a player cannot make a valid move on their turn the game ends and that player loses. Given arrays a and b, determine whether Alice can force a win when both play optimally.

Key Insights

  • The “closely greater” requirement forces a move to be not only lexicographically greater but also to keep the first letter “close” (either the same or one letter ahead).
  • Both players’ word lists are sorted; hence, once a word is “too low” (i.e. not greater than the current word) it cannot be used later.
  • When there are several options, playing the smallest valid word minimizes the “jump” in lexicographic order and restricts the opponent’s choices – so under optimal play the “greedy” choice is best.
  • The game can be simulated by maintaining pointers into the two sorted arrays and, on each turn, “fast‐forwarding” (skipping words that are either not greater than the current word or whose first letter is not allowable based on the last-played word).

Space and Time Complexity

Time Complexity: O(n + m) where n and m are the lengths of a and b respectively (each word is examined at most once). Space Complexity: O(1) extra space (besides the space used for the input arrays).

Solution

The approach is to simulate the game turn by turn. The simulation works as follows:

  1. Initialize by having Alice play her smallest word (the first element in a). Set the “current word” to that word.
  2. For the next turn the allowed set of first letters is determined from the current word. If the current word starts with letter L then the allowed letters are { L, nextLetter } (with nextLetter defined only if L isn’t ‘z’; otherwise only L is allowed).
  3. For the current player (starting with Bob after the initial move), search in their sorted list from the current pointer (i.e. the first unused word) for the first word that is strictly lexicographically greater than the current word and whose first character is in the allowed set. • If a candidate word is found, update the “current word” to this candidate and mark that word as used (advance the pointer). • If no candidate is found, the current player loses.
  4. Alternate turns until one player cannot move.
  5. Under optimal play – where choosing the smallest valid candidate limits the opponent’s moves most – this simulation determines whether Alice eventually wins.

Using this greedy simulation we “mimic” optimal play in O(n + m) time with two pointers and binary‐search–like skipping.

Code Solutions

# Python solution with detailed comments
def canAliceWin(a, b):
    # pointers for both lists (each word once used is skipped)
    pointer_a, pointer_b = 0, 0
    n, m = len(a), len(b)
    
    # First move: Alice must play her smallest word.
    if n == 0:
        return False
    current_word = a[pointer_a]
    pointer_a += 1  # mark the word as used
    
    # 0 represents Alice's turn, 1 represents Bob's turn.
    turn = 1  # since Bob goes next
    
    # Helper function to get allowed starting characters given last word.
    def allowed_letters(word):
        first = word[0]
        allowed = {first}
        if first != 'z':
            allowed.add(chr(ord(first)+1))
        return allowed
    
    # Simulate game turns.
    while True:
        allowed = allowed_letters(current_word)
        if turn == 0:
            # Alice's turn, try to find her next valid word from a.
            found = False
            while pointer_a < n:
                candidate = a[pointer_a]
                # candidate must be lexicographically greater than current_word
                # and its first letter must be in allowed
                if candidate > current_word and candidate[0] in allowed:
                    found = True
                    current_word = candidate
                    pointer_a += 1
                    break
                pointer_a += 1  # skip candidate if invalid
            if not found:
                # Alice cannot move so she loses.
                return False
        else:
            # Bob's turn, search in Bob's list b.
            found = False
            while pointer_b < m:
                candidate = b[pointer_b]
                if candidate > current_word and candidate[0] in allowed:
                    found = True
                    current_word = candidate
                    pointer_b += 1
                    break
                pointer_b += 1
            if not found:
                # Bob cannot move, so Alice wins.
                return True
        # Alternate player turn.
        turn ^= 1

# Example usage:
# a1 = ["avokado","dabar"]
# b1 = ["brazil"]
# print(canAliceWin(a1, b1))  # Expected output: False
← Back to All Questions