Problem

Alice and Bob are playing a game on a string.

You are given a string s, Alice and Bob will take turns playing the following game where Alice starts first :

  • On Alice’s turn, she has to remove any non-empty substring from s that contains an odd number of vowels.
  • On Bob’s turn, he has to remove any non-empty substring from s that contains an even number of vowels.

The first player who cannot make a move on their turn loses the game. We assume that both Alice and Bob play optimally.

Return true if Alice wins the game, and false otherwise.

The English vowels are: a, e, i, o, and u.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


Input: s = "leetcoder"

Output: true

Explanation:  
Alice can win the game as follows:

  * Alice plays first, she can delete the underlined substring in `s = "_**leetco**_ der"` which contains 3 vowels. The resulting string is `s = "der"`.
  * Bob plays second, he can delete the underlined substring in `s = "_**d**_ er"` which contains 0 vowels. The resulting string is `s = "er"`.
  * Alice plays third, she can delete the whole string `s = "**_er_** "` which contains 1 vowel.
  * Bob plays fourth, since the string is empty, there is no valid play for Bob. So Alice wins the game.

Example 2

1
2
3
4
5
6
7


Input: s = "bbcd"

Output: false

Explanation:  
There is no valid play for Alice in her first turn, so Alice loses the game.

Constraints

  • 1 <= s.length <= 10^5
  • s consists only of lowercase English letters.

Solution

Method 1 – Parity and Game Theory

Intuition

The key is to count the number of vowels in the string. If the number of vowels is odd, Alice can always win by removing the whole string (which is a valid move for her). If the number of vowels is even and greater than zero, Bob can always win by removing the whole string on his turn. If there are no vowels, Alice cannot make a move and loses.

Approach

Count the number of vowels in the string. If the count is odd, Alice wins. If the count is even and greater than zero, Bob wins. If there are no vowels, Alice loses immediately.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
public:
    bool aliceWins(string s) {
        int cnt = 0;
        for (char c : s) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cnt++;
        }
        return cnt % 2 == 1;
    }
};
1
2
3
4
5
6
7
8
9

func aliceWins(s string) bool {
    cnt := 0
    for _, c := range s {
        if c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u' {
            cnt++
        }
    }
    return cnt%2 == 1
}
1
2
3
4
5
6
7
8
9

class Solution {
    public boolean aliceWins(String s) {
        int cnt = 0;
        for (char c : s.toCharArray()) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cnt++;
        }
        return cnt % 2 == 1;
    }
}
1
2
3
4
5
6
7
8
9

class Solution {
    fun aliceWins(s: String): Boolean {
        var cnt = 0
        for (c in s) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') cnt++
        }
        return cnt % 2 == 1
    }
}
1
2
3
4
5

class Solution:
    def aliceWins(self, s: str) -> bool:
        vowels = set('aeiou')
        cnt = sum(1 for c in s if c in vowels)
        return cnt % 2 == 1
1
2
3
4

pub fn alice_wins(s: &str) -> bool {
    let cnt = s.chars().filter(|&c| matches!(c, 'a' | 'e' | 'i' | 'o' | 'u')).count();
    cnt % 2 == 1
}
1
2
3
4
5
6
7

function aliceWins(s: string): boolean {
    let cnt = 0;
    for (const c of s) {
        if ('aeiou'.includes(c)) cnt++;
    }
    return cnt % 2 === 1;
}

Complexity

  • ⏰ Time complexity: O(n) — One pass to count vowels.
  • 🧺 Space complexity: O(1) — Only a few variables are used.