The Wording Game - Practice Coding Problems

The Wording Game - Problem

Array Math Two Pointers String Greedy Game Theory Hard

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:

w is lexicographically greater than z
If 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

For example, the word "care" is closely greater than "book" and "car", but is not closely greater than "ant" or "cook".

Input & Output

Example 1 — Alice Wins

$ Input: a = ["aa", "ab"], b = ["ba", "bb"]

› Output: true

💡 Note: Alice starts with "aa". Bob can play "ba" (closely greater). Alice can then play "ab" (closely greater than "ba"). Bob has no valid moves since "bb" is not closely greater than "ab" (b+1=c, but "bb" < "cb").

Example 2 — Bob Wins

$ Input: a = ["ca"], b = ["da", "db"]

› Output: false

💡 Note: Alice starts with "ca". Bob can play "da" (closely greater: d = c+1). Alice has no more words. Bob wins.

Example 3 — Equal Start

$ Input: a = ["ba"], b = ["bb"]

› Output: false

💡 Note: Alice starts with "ba". Bob can play "bb" (closely greater: same first letter 'b' and "bb" > "ba"). Alice has no moves left.

Constraints

1 ≤ a.length, b.length ≤ 1000
1 ≤ a[i].length, b[i].length ≤ 100
a and b consist of lowercase English letters only
All strings in a and b are distinct
Arrays a and b are lexicographically sorted

Visualization

Tap to expand

Understanding the Visualization

Setup

Alice has ["aa","ab"], Bob has ["ba","bb"]

Game Play

Alice starts "aa" → Bob plays "ba" → Alice plays "ab"

Victory

Bob has no valid moves, Alice wins

Key Takeaway

🎯 Key Insight: Success depends on forcing the opponent into positions with no valid closely greater words

Asked in

G Google 15 M Microsoft 12 A Amazon 8

The key insight is recognizing this as a game theory problem where optimal play from both sides determines the winner. The best approach uses recursive simulation with memoization to explore all possible game states. Time: O(2^(n+m)), Space: O(n+m), though a greedy counting heuristic can provide faster approximation.

Common Approaches

Approach	Time	Space	Notes
✓ Greedy Counting Strategy	O((n+m) × 26)	O(26)	Count available moves for each player using greedy approach
Recursive Game Simulation	O(2^(n+m))	O(n+m)	Simulate all possible game sequences using recursion

Greedy Counting Strategy — Algorithm Steps

Count words available for each starting letter
For each possible game state, count remaining moves
Alice wins if she can force Bob into a position with no moves

Visualization

Tap to expand

Step-by-Step Walkthrough

Count

Count words by first letter for both players

Analyze

Calculate Alice's strategic advantage

Decide

Alice wins if she has enough advantage

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool solution(char a[][100], int aSize, char b[][100], int bSize) {
    int aCount[26] = {0};
    int bCount[26] = {0};
    
    for (int i = 0; i < aSize; i++) {
        aCount[a[i][0] - 'a']++;
    }
    
    for (int i = 0; i < bSize; i++) {
        bCount[b[i][0] - 'a']++;
    }
    
    int aliceAdvantage = 0;
    for (int i = 0; i < 26; i++) {
        if (i <= 24) {
            int next = (i + 1 < 26) ? bCount[i + 1] : 0;
            aliceAdvantage += aCount[i] - next;
        }
        aliceAdvantage += aCount[i] - bCount[i];
    }
    
    return aliceAdvantage > 0;
}

int main() {
    char a[100][100], b[100][100];
    int aSize = 0, bSize = 0;
    
    // Simplified parsing
    bool result = solution(a, aSize, b, bSize);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O((n+m) × 26)

For each of 26 letters, scan through all words once

✓ Linear Growth

Space Complexity

O(26)

Arrays to count words by starting letter

✓ Linear Space

12.0K Views

Medium Frequency

~35 min Avg. Time

245 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy Counting Strategy — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler