Vowels Game in a String
Alice and Bob are playing a game on a string.
You are given a string s. Alice and Bob take turns playing the following game, where Alice starts first:
- On Alice's turn, she has to remove any non-empty substring from
sthat contains an odd number of vowels. - On Bob's turn, he has to remove any non-empty substring from
sthat 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.
Example 1
Input
s = "leetcoder"Output
trueAlice can delete a substring with 3 vowels, Bob can delete a substring with 0 vowels, and Alice can then delete the remaining string with 1 vowel, leaving Bob with no valid move.
Example 2
Input
s = "bbcd"Output
falseThere 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.