3227. Vowels Game in a String
Description
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
.
Example 1:
Input: s = "leetcoder"
Output: true
Explanation:
Alice can win the game as follows:
- Alice plays first, she can delete the underlined substring in
s = "leetcoder"
which contains 3 vowels. The resulting string iss = "der"
. - Bob plays second, he can delete the underlined substring in
s = "der"
which contains 0 vowels. The resulting string iss = "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:
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 <= 105
s
consists only of lowercase English letters.
Solutions
Solution 1: Brain Teaser
Let's denote the number of vowels in the string as $k$.
If $k = 0$, meaning there are no vowels in the string, then Little Red cannot remove any substring, and Little Ming wins directly.
If $k$ is odd, then Little Red can remove the entire string, resulting in a direct win for Little Red.
If $k$ is even, then Little Red can remove $k - 1$ vowels, leaving one vowel in the string. In this case, Little Ming cannot remove any substring, leading to a direct win for Little Red.
In conclusion, if the string contains vowels, then Little Red wins; otherwise, Little Ming wins.
The time complexity is $O(n)$, where $n$ is the length of the string $s$. The space complexity is $O(1)$.
1 2 3 4 |
|
1 2 3 4 5 6 7 8 9 10 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 |
|
1 2 3 4 5 6 7 8 9 |
|