Problem

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".

A string s is lexicographically****greater than a string t if in the first position where s and t differ, string s has a letter that appears later in the alphabet than the corresponding letter in t. If the first min(s.length, t.length) characters do not differ, then the longer string is the lexicographically greater one.

Examples

Example 1:

1
2
3
4
5
Input: a = ["avokado","dabar"], b = ["brazil"]
Output: false
Explanation: Alice must start the game by playing the word "avokado" since it's her smallest word, then Bob plays his only word, "brazil", which he can play because its first letter, 'b', is the letter after Alice's word's first letter, 'a'.
Alice can't play a word since the first letter of the only word left is not equal to 'b' or the letter after 'b', 'c'.
So, Alice loses, and the game ends.

Example 2:

1
2
3
4
5
Input: a = ["ananas","atlas","banana"], b = ["albatros","cikla","nogomet"]
Output: true
Explanation: Alice must start the game by playing the word "ananas".
Bob can't play a word since the only word he has that starts with the letter 'a' or 'b' is "albatros", which is smaller than Alice's word.
So Alice wins, and the game ends.

Example 3:

1
2
3
4
5
Input: a = ["hrvatska","zastava"], b = ["bijeli","galeb"]
Output: true
Explanation: Alice must start the game by playing the word "hrvatska".
Bob can't play a word since the first letter of both of his words are smaller than the first letter of Alice's word, 'h'.
So Alice wins, and the game ends.

Constraints:

  • 1 <= a.length, b.length <= 10^5
  • a[i] and b[i] consist only of lowercase English letters.
  • a and b are lexicographically sorted.
  • All the words in a and b combined are distinct.
  • The sum of the lengths of all the words in a and b combined does not exceed 106.

Solution

Method 1 - Two Pointers and Greedy Simulation

We simulate the game using two pointers for Alice and Bob, always picking the next valid word for each player. The key is to efficiently find the next word that is closely greater than the last played word, using the sorted property and binary search.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
class Solution {
public:
    bool canAliceWin(vector<string>& a, vector<string>& b) {
        auto next = [](const vector<string>& arr, const string& last) -> int {
            char c1 = last[0];
            for (int d = 0; d <= 1; ++d) {
                char c = c1 + d;
                auto it = lower_bound(arr.begin(), arr.end(), string(1, c));
                while (it != arr.end() && (*it)[0] == c) {
                    if (*it > last) return it - arr.begin();
                    ++it;
                }
            }
            return -1;
        };
        int i = 0, j = 0, n = a.size(), m = b.size();
        string last = a[0];
        vector<bool> usedA(n, false), usedB(m, false);
        usedA[0] = true;
        bool aliceTurn = false;
        while (true) {
            if (!aliceTurn) {
                int idx = next(b, last);
                if (idx == -1 || usedB[idx]) return true;
                usedB[idx] = true;
                last = b[idx];
            } else {
                int idx = next(a, last);
                if (idx == -1 || usedA[idx]) return false;
                usedA[idx] = true;
                last = a[idx];
            }
            aliceTurn = !aliceTurn;
        }
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import java.util.*;
class Solution {
    public boolean canAliceWin(String[] a, String[] b) {
        int n = a.length, m = b.length;
        boolean[] usedA = new boolean[n], usedB = new boolean[m];
        String last = a[0];
        usedA[0] = true;
        boolean aliceTurn = false;
        while (true) {
            if (!aliceTurn) {
                int idx = next(b, usedB, last);
                if (idx == -1) return true;
                usedB[idx] = true;
                last = b[idx];
            } else {
                int idx = next(a, usedA, last);
                if (idx == -1) return false;
                usedA[idx] = true;
                last = a[idx];
            }
            aliceTurn = !aliceTurn;
        }
    }
    private int next(String[] arr, boolean[] used, String last) {
        char c1 = last.charAt(0);
        for (int d = 0; d <= 1; ++d) {
            char c = (char)(c1 + d);
            for (int i = Arrays.binarySearch(arr, String.valueOf(c)); i < arr.length && i >= 0 && arr[i].charAt(0) == c; ++i) {
                if (!used[i] && arr[i].compareTo(last) > 0) return i;
            }
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
from bisect import bisect_left
from typing import List
class Solution:
    def canAliceWin(self, a: List[str], b: List[str]) -> bool:
        def next_idx(arr, used, last):
            c1 = last[0]
            for d in range(2):
                c = chr(ord(c1) + d)
                i = bisect_left(arr, c)
                while i < len(arr) and arr[i][0] == c:
                    if not used[i] and arr[i] > last:
                        return i
                    i += 1
            return -1
        n, m = len(a), len(b)
        usedA = [False]*n
        usedB = [False]*m
        last = a[0]
        usedA[0] = True
        aliceTurn = False
        while True:
            if not aliceTurn:
                idx = next_idx(b, usedB, last)
                if idx == -1:
                    return True
                usedB[idx] = True
                last = b[idx]
            else:
                idx = next_idx(a, usedA, last)
                if idx == -1:
                    return False
                usedA[idx] = True
                last = a[idx]
            aliceTurn = not aliceTurn
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
use std::collections::BTreeSet;
impl Solution {
    pub fn can_alice_win(a: Vec<String>, b: Vec<String>) -> bool {
        fn next(arr: &Vec<String>, used: &BTreeSet<usize>, last: &str) -> Option<usize> {
            let c1 = last.chars().next().unwrap();
            for d in 0..=1 {
                let c = ((c1 as u8) + d) as char;
                for (i, s) in arr.iter().enumerate() {
                    if used.contains(&i) { continue; }
                    if s.chars().next().unwrap() == c && s > last {
                        return Some(i);
                    }
                }
            }
            None
        }
        let n = a.len();
        let m = b.len();
        let mut used_a = BTreeSet::new();
        let mut used_b = BTreeSet::new();
        let mut last = a[0].clone();
        used_a.insert(0);
        let mut alice_turn = false;
        loop {
            if !alice_turn {
                if let Some(idx) = next(&b, &used_b, &last) {
                    used_b.insert(idx);
                    last = b[idx].clone();
                } else {
                    return true;
                }
            } else {
                if let Some(idx) = next(&a, &used_a, &last) {
                    used_a.insert(idx);
                    last = a[idx].clone();
                } else {
                    return false;
                }
            }
            alice_turn = !alice_turn;
        }
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function canAliceWin(a: string[], b: string[]): boolean {
    const usedA = new Array(a.length).fill(false);
    const usedB = new Array(b.length).fill(false);
    let last = a[0];
    usedA[0] = true;
    let aliceTurn = false;
    function next(arr: string[], used: boolean[], last: string): number {
        const c1 = last[0];
        for (let d = 0; d <= 1; ++d) {
            const c = String.fromCharCode(c1.charCodeAt(0) + d);
            let i = arr.findIndex((s, idx) => !used[idx] && s[0] === c && s > last);
            if (i !== -1) return i;
        }
        return -1;
    }
    while (true) {
        if (!aliceTurn) {
            const idx = next(b, usedB, last);
            if (idx === -1) return true;
            usedB[idx] = true;
            last = b[idx];
        } else {
            const idx = next(a, usedA, last);
            if (idx === -1) return false;
            usedA[idx] = true;
            last = a[idx];
        }
        aliceTurn = !aliceTurn;
    }
}

Complexity

  • ⏰ Time complexity: O(N log N) (due to binary search and up to N moves)
  • 🧺 Space complexity: O(N)