In this guide, you will get 3227. Vowels Game in a String LeetCode Solution with the best time and space complexity. The solution to Vowels Game in a String problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
3227. Vowels Game in a String LeetCode Solution in C++
class Solution {
public:
bool doesAliceWin(string s) {
// Let k be the number of vowels in s.
// 1. If k == 0, Bob wins since Alice has no vowels to pick.
// 2. If k % 2 == 1, Alice wins since Alice can pick the entire string.
// 3. If k % 2 == 0, Alice wins since Alice can pick (k - 1) vowels,
// then Bob will either pick a substring containing 0 vowels, resulting in
// Alice picking the remaining entire string, or Bob couldn't pick at all
// (the last vowel).
return ranges::any_of(s, [this](char c) { return isVowel(c); });
}
private:
bool isVowel(char c) {
static constexpr string_view kVowels = "aeiou";
return kVowels.find(c) != string_view::npos;
}
}; /* code provided by PROGIEZ */
3227. Vowels Game in a String LeetCode Solution in Java
class Solution {
public boolean doesAliceWin(String s) {
// Let k be the number of vowels in s.
// 1. If k == 0, Bob wins since Alice has no vowels to pick.
// 2. If k % 2 == 1, Alice wins since Alice can pick the entire string.
// 3. If k % 2 == 0, Alice wins since Alice can pick (k - 1) vowels,
// then Bob will either pick a substring containing 0 vowels, resulting in
// Alice picking the remaining entire string, or Bob couldn't pick at all
// (the last vowel).
return s.chars().anyMatch(c -> isVowel((char) c));
}
private boolean isVowel(char c) {
return "aeiou".indexOf(Character.toLowerCase(c)) != -1;
}
} // code provided by PROGIEZ
3227. Vowels Game in a String LeetCode Solution in Python
class Solution:
def doesAliceWin(self, s: str) -> bool:
# Let k be the number of vowels in s.
# 1. If k == 0, Bob wins since Alice has no vowels to pick.
# 2. If k % 2 == 1, Alice wins since Alice can pick the entire string.
# 3. If k % 2 == 0, Alice wins since Alice can pick (k - 1) vowels,
# then Bob will either pick a substring containing 0 vowels, resulting in
# Alice picking the remaining entire string, or Bob couldn't pick at all
# (the last vowel).
kVowels = 'aeiou'
return any(c in kVowels for c in s) # code by PROGIEZ
