3227. Vowels Game in a String

Posted on Edited on In

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:

1
2
3
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
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.

Hints/Notes

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool doesAliceWin(string s) {
        int numVowels = 0;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' ||
                s[i] == 'u') {
                numVowels++;
            }
        }
        if (numVowels == 0) {
            return false;
        }
        return true;
    }
};