2868. The Wording Game


Problem Description

Alice and Bob are playing a game using two lexicographically sorted lists of strings, a and b. The game is turn-based, starting with Alice. On a player's turn, they must choose a word from their list that is "closely greater" than the last word played. A word w is considered "closely greater" than a word z if w is lexicographically greater than z, and the first letter of w is either identical to or immediately follows the first letter of z in the alphabet. A player loses if they cannot play a word on their turn. The problem asks us to determine if Alice can win the game, assuming both players play optimally.

For instance, "car" can be followed by "care" or "cat" but not by "ant" or "book". If the previous word is "cook," the next valid word could be "cool" or "coop," but not "card," since "d" is not the letter immediately after "c".

The lexicographical comparison works in a way where the difference between two strings is found at the first differing character; the string with the higher alphabetical character at that position is considered greater. If there's no difference within the shorter length of the two strings, the longer string is deemed greater.

Intuition

The given solution approach is a simulation of the game, adhering to the rules described. The intuition behind this simulation is to track the current word and the indices for Alice and Bob's lists, marking whose turn it is with k (0 for Alice, 1 for Bob). Both players start with the smallest possible valid word from their respective lists.

The key observation here is to decide, for the current player, if their next word in the list is a valid "closely greater" word than the last word played. Because the lists are sorted lexicographically, the players can simply iterate through their lists in order, checking each word until they find a suitable one or run out of words.

Alice starts the game, so we begin with her list (except the first word, as it's already played). At each player's turn, we consider the following:

  • If the player has no more words to play (reaching the end of their list), they lose.
  • If the current word on the player's list is "closely greater," it is played, and the turn switches to the other player.
  • If the current word is not valid, we move to the next word in the list.

The algorithm toggles between the players and iterates through both lists until it finds the outcome (either Alice can't play and loses, or Bob can't play and thus Alice wins). By following this optimal strategy simulation for both Alice and Bob, the solution is able to determine if Alice has a winning strategy.

Learn more about Math and Two Pointers patterns.

Solution Approach

The implementation of the game simulation involves a while loop that continues indefinitely until a player cannot make a move. The solution relies on a few important observations about the nature of the game and the structure of the data:

  1. Lexicographic Order: Since both lists a and b are sorted lexicographically, once a player cannot find a "closely greater" word after a certain word in their list, no word thereafter in their list can be a valid play. This is because each subsequent word is not only lexicographically greater but also differs by more than one letter from the beginning of the word, violating the "closely greater" condition.

  2. Alternating Turns: The variable k indicates which player's turn it is. It starts with Alice (k = 0), and every time a valid move is made, k is toggled (k ^= 1). If k is 1 (Bob's turn), the simulation checks Bob's list; otherwise, it checks Alice's.

  3. Pointer Iteration: Two pointers (i for Alice's index and j for Bob's index) iterate through their respective lists. These increase independently as each player takes their turn, meaning they only look for a "closely greater" word from where they left off last time.

  4. Valid Move Check: On a player's turn, for their current word to be a valid "closely greater" move, one of two conditions must be met:

    • The first letters of the current word and the last played word are the same, and the current word is lexicographically greater.
    • The first letter of the current word is exactly one letter after the first letter of the last played word in the alphabet.

This is implemented using conditional statements checking b[j][0] == w[0] and b[j] > w or ord(b[j][0]) - ord(w[0]) == 1 for Bob, and similarly for Alice.

Once the simulation finds that a player cannot play any more words (the pointer has reached the end of their list), it exits the loop. This is programmed as if j == len(b) for Bob (Alice wins), and if i == len(a) for Alice (Bob wins).

This results in a neat and efficient simulation of the game, effectively modeling each player's possible moves without having to backtrack or reconsider previous decisions. The efficiency stems from both the sorted nature of the lists and the binary nature of the turn-taking, which allows the solution to straightforwardly execute the optimal strategy simulation for both players.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a small example using the solution approach described.

Assume the sorted lists for Alice and Bob are as follows:

Alice's list a: ["arc", "bit", "cart"] Bob's list b: ["art", "car", "cute", "dart"]

Now, let's simulate the game:

  1. Alice starts (k = 0) and plays the smallest word from her list, which is "arc".
  2. It's now Bob's turn (k = 1). The first word in his list, "art", is "closely greater" to "arc" (same start letter and lexicographically greater), so he plays "art".
  3. Alice can now no longer play "arc" or "bit" because they are not "closely greater" than "art". She plays her next valid word "cart".
  4. Bob's next word is "car", but "car" isn't valid because it's not greater than "cart". He skips to "cute", which also isn't valid (the first letter 'c' doesn't follow 'c' directly in the alphabet), so he has to play "dart".
  5. Alice can't play "arc" or "bit" as they were already invalid. Her last word is "cart", which is not "closely greater" than "dart", and there are no remaining words in her list.
  6. Alice fails to play a move, so Bob wins.

In this walkthrough, Bob has won the game by playing his words efficiently, and Alice reaches the end of her list without a valid move to make. This example demonstrates the solution approach where each player, on their turn, chooses the smallest valid "closely greater" word from their list, until one player ultimately cannot make a move and loses.

Solution Implementation

1class Solution:
2    def canAliceWin(self, alice_cards: List[str], bob_cards: List[str]) -> bool:
3        # Initialize pointers for Alice and Bob's card and a flag for Alice's turn.
4        alice_index, bob_index = 1, 0
5        is_alice_turn = True
6      
7        # Winning card starts as Alice's first card.
8        winning_card = alice_cards[0]
9      
10        # Loop until break condition is met.
11        while True:
12            # Check if it's Alice's turn.
13            if is_alice_turn:
14                # If Bob has no more cards, Alice wins.
15                if bob_index == len(bob_cards):
16                    return True
17                # Compare cards and update the winning card if conditions are met.
18                if (bob_cards[bob_index][0] == winning_card[0] and bob_cards[bob_index] > winning_card) \
19                or ord(bob_cards[bob_index][0]) - ord(winning_card[0]) == 1:
20                    winning_card = bob_cards[bob_index]
21                    # Toggle the turn.
22                    is_alice_turn = not is_alice_turn
23                # Move to the next card for Bob.
24                bob_index += 1
25            else:
26                # If Alice has no more cards, Bob wins, hence Alice loses.
27                if alice_index == len(alice_cards):
28                    return False
29                # Compare cards and update the winning card if conditions are met.
30                if (alice_cards[alice_index][0] == winning_card[0] and alice_cards[alice_index] > winning_card) \
31                or ord(alice_cards[alice_index][0]) - ord(winning_card[0]) == 1:
32                    winning_card = alice_cards[alice_index]
33                    # Toggle the turn.
34                    is_alice_turn = not is_alice_turn
35                # Move to the next card for Alice.
36                alice_index += 1
37
1class Solution {
2    public boolean canAliceWin(String[] aliceCards, String[] bobCards) {
3        // Initialize pointer i for Alice's cards and j for Bob's cards
4        int aliceIndex = 1, bobIndex = 0;
5      
6        // Boolean flag to keep track of whose turn it is; true for Alice's turn and false for Bob's turn
7        boolean isAliceTurn = true;
8      
9        // The card to compare with, beginning with the first card of Alice's
10        String currentWinningCard = aliceCards[0];
11      
12        // Infinite loop to simulate the turns taken by Alice and Bob
13        while (true) {
14            // If it's Alice's turn
15            if (isAliceTurn) {
16                // If all Bob's cards are played, Alice wins
17                if (bobIndex == bobCards.length) {
18                    return true;
19                }
20
21                // Alice can play a card only if it's directly greater than the current winning card,
22                // or if it's one rank higher regardless of the suit. If played, swap turns
23                if ((bobCards[bobIndex].charAt(0) == currentWinningCard.charAt(0) && currentWinningCard.compareTo(bobCards[bobIndex]) < 0)
24                    || (bobCards[bobIndex].charAt(0) - currentWinningCard.charAt(0) == 1)) {
25                    currentWinningCard = bobCards[bobIndex];
26                    isAliceTurn = !isAliceTurn;
27                }
28                // Move to the next card in Bob's deck
29                ++bobIndex;
30            } else {
31                // If all Alice's cards are played, Bob wins, hence Alice loses
32                if (aliceIndex == aliceCards.length) {
33                    return false;
34                }
35
36                // Bob can play a card only if it's directly greater than the current winning card,
37                // or if it's one rank higher regardless of the suit. If played, swap turns
38                if ((aliceCards[aliceIndex].charAt(0) == currentWinningCard.charAt(0) && currentWinningCard.compareTo(aliceCards[aliceIndex]) < 0)
39                    || (aliceCards[aliceIndex].charAt(0) - currentWinningCard.charAt(0) == 1)) {
40                    currentWinningCard = aliceCards[aliceIndex];
41                    isAliceTurn = !isAliceTurn;
42                }
43                // Move to the next card in Alice's deck
44                ++aliceIndex;
45            }
46        }
47    }
48}
49
1class Solution {
2public:
3    bool canAliceWin(vector<string>& aliceWords, vector<string>& bobWords) {
4        int aliceIndex = 1; // Start with the second word for Alice as she starts the game with the first word
5        int bobIndex = 0;   // Start with the first word for Bob
6        bool isAliceTurn = true; // Alice starts the game, so it's her turn initially
7        string currentWord = aliceWords[0]; // Set the current word as Alice's first word
8      
9        // Continue till a decision can be reached
10        while (true) {
11            if (isAliceTurn) { // If it's Alice's turn
12                if (bobIndex == bobWords.size()) { // If Bob has no more words to play, Alice wins
13                    return true;
14                }
15                // Check if the first letter of Bob's current word follows the current word alphabetically or is the same starting letter and lexicographically greater
16                if ((bobWords[bobIndex][0] == currentWord[0] && currentWord < bobWords[bobIndex]) || bobWords[bobIndex][0] - currentWord[0] == 1) {
17                    currentWord = bobWords[bobIndex]; // Update the current word
18                    isAliceTurn ^= 1; // Toggle the turn to Bob's
19                }
20                bobIndex++; // Move to Bob's next word
21            } else { // If it's Bob's turn
22                if (aliceIndex == aliceWords.size()) { // If Alice has no more words to play, Bob wins, so Alice loses
23                    return false;
24                }
25                // Check if the first letter of Alice's current word follows the current word alphabetically or is the same starting letter and lexicographically greater
26                if ((aliceWords[aliceIndex][0] == currentWord[0] && currentWord < aliceWords[aliceIndex]) || aliceWords[aliceIndex][0] - currentWord[0] == 1) {
27                    currentWord = aliceWords[aliceIndex]; // Update the current word
28                    isAliceTurn ^= 1; // Toggle the turn to Alice's
29                }
30                aliceIndex++; // Move to Alice's next word
31            }
32        }
33    }
34};
35
1function canAliceWin(aliceCards: string[], bobCards: string[]): boolean {
2    // Initialize indices for Alice (i) and Bob (j), and a flag (turnFlag) to track whose turn it is.
3    // Alice starts with the first card in her array (index 0).
4    let aliceIndex = 1;
5    let bobIndex = 0;
6    let turnFlag = 1; // 1 for Alice's turn, 0 for Bob's turn.
7    let currentWinningCard = aliceCards[0]; // Current winning card, starting with Alice's first card.
8
9    // Continue the game until a winner is determined.
10    while (true) {
11        if (turnFlag === 1) { // If it's Alice's turn
12            if (bobIndex === bobCards.length) {
13                return true; // Alice wins if Bob has no more cards.
14            }
15
16            // Check if Bob has a card that beats the current winning card, either by suit or rank.
17            if ((bobCards[bobIndex][0] === currentWinningCard[0] && currentWinningCard < bobCards[bobIndex]) ||
18                bobCards[bobIndex].charCodeAt(0) - currentWinningCard.charCodeAt(0) === 1) {
19                currentWinningCard = bobCards[bobIndex]; // Bob takes the lead with a new winning card.
20                turnFlag ^= 1; // Toggle the turn flag to switch turns.
21            }
22
23            bobIndex++; // Move to Bob's next card.
24        } else { // If it's Bob's turn
25            if (aliceIndex === aliceCards.length) {
26                return false; // Bob wins if Alice has no more cards.
27            }
28          
29            // Check if Alice has a card that beats the current winning card, either by suit or rank.
30            if ((aliceCards[aliceIndex][0] === currentWinningCard[0] && currentWinningCard < aliceCards[aliceIndex]) ||
31                aliceCards[aliceIndex].charCodeAt(0) - currentWinningCard.charCodeAt(0) === 1) {
32                currentWinningCard = aliceCards[aliceIndex]; // Alice takes the lead with a new winning card.
33                turnFlag ^= 1; // Toggle the turn flag to switch turns.
34            }
35
36            aliceIndex++; // Move to Alice's next card.
37        }
38    }
39}
40

Time and Space Complexity

The time complexity of the provided code is O(m + n), where m is the length of list a and n is the length of list b. This is because the code involves a single while loop with no nested loops, and it traverses each list at most once, incrementally iterating the indices i and j.

The space complexity of the code is O(1). This is because the amount of additional memory used does not depend on the size of the input lists a and b, but is rather constant. Only a fixed amount of space for the variables i, j, k, and w is needed, regardless of input size.

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


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Consider the classic dynamic programming of longest increasing subsequence:

Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.

For example, the length of LIS for [50, 3, 10, 7, 40, 80] is 4 and LIS is [3, 7, 40, 80].

What is the recurrence relation?


Recommended Readings

Want a Structured Path to Master System Design Too? Donā€™t Miss This!


Load More