Skip to content

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 is s = "der".
  • Bob plays second, he can delete the underlined substring in s = "der" 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:

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
class Solution:
    def doesAliceWin(self, s: str) -> bool:
        vowels = set("aeiou")
        return any(c in vowels for c in s)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution {
    public boolean doesAliceWin(String s) {
        for (int i = 0; i < s.length(); ++i) {
            if ("aeiou".indexOf(s.charAt(i)) != -1) {
                return true;
            }
        }
        return false;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution {
public:
    bool doesAliceWin(string s) {
        string vowels = "aeiou";
        for (char c : s) {
            if (vowels.find(c) != string::npos) {
                return true;
            }
        }
        return false;
    }
};

1
2
3
4
5
6
7
8
9
func doesAliceWin(s string) bool {
    vowels := "aeiou"
    for _, c := range s {
        if strings.ContainsRune(vowels, c) {
            return true
        }
    }
    return false
}

1
2
3
4
5
6
7
8
9
function doesAliceWin(s: string): boolean {
    const vowels = 'aeiou';
    for (const c of s) {
        if (vowels.includes(c)) {
            return true;
        }
    }
    return false;
}

Comments