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

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

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

Alice wins if there is at least one vowel in the string, because she can always remove a substring containing a vowel on her first turn. If there are no vowels, Alice cannot make a move and loses.

Approach

  1. Iterate through the string.
  2. If you find any vowel (a, e, i, o, or u), Alice can win immediately.
  3. If no vowels are found, Alice loses.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    bool doesAliceWin(string s) {
        for (char ch : s) {
            if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
                return true;
            }
        }
        return false;
    }
};
1
2
3
4
5
6
7
8

func doesAliceWin(s string) bool {
    for _, ch := range s {
        if ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' {
            return true
        }
    }
    return false
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
    public boolean doesAliceWin(String s) {
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
                return true;
            }
        }
        return false;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    fun doesAliceWin(s: String): Boolean {
        for (ch in s) {
            if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') {
                return true
            }
        }
        return false
    }
}
1
2
3
4
5
6

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        for ch in s:
            if ch in 'aeiou':
                return True
        return False
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

impl Solution {
    pub fn does_alice_win(s: &str) -> bool {
        for ch in s.chars() {
            if matches!(ch, 'a' | 'e' | 'i' | 'o' | 'u') {
                return true;
            }
        }
        false
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution {
    doesAliceWin(s: string): boolean {
        for (const ch of s) {
            if ('aeiou'.includes(ch)) {
                return true;
            }
        }
        return false;
    }
}

Complexity

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