Vowels Game in a String
Problem
Alice and Bob alternate turns on a string s, with Alice going first. On her turn Alice removes any non-empty substring containing an odd number of vowels; on his turn Bob removes any non-empty substring containing an even number of vowels (zero counts as even). The first player who cannot move loses. With both playing optimally, return true if Alice wins. Vowels are a, e, i, o, u.
s = "leetcoder"truedef doesAliceWin(s):
vowels = set("aeiou") # the five English vowels
# Game theory result: with optimal play Alice loses
# only when the string has NO vowels at all. Otherwise
# she always wins, so we just look for one vowel.
for ch in s:
if ch in vowels:
return True # a vowel exists -> Alice wins
return False # no vowels -> Bob winsfunction doesAliceWin(s) {
const vowels = new Set(["a", "e", "i", "o", "u"]);
// Game theory result: with optimal play Alice loses
// only when the string has NO vowels at all. Otherwise
// she always wins, so we just look for one vowel.
for (const ch of s) {
if (vowels.has(ch)) {
return true; // a vowel exists -> Alice wins
}
}
return false; // no vowels -> Bob wins
}boolean doesAliceWin(String s) {
String vowels = "aeiou"; // the five English vowels
// Game theory result: with optimal play Alice loses
// only when the string has NO vowels at all. Otherwise
// she always wins, so we just look for one vowel.
for (int i = 0; i < s.length(); i++) {
if (vowels.indexOf(s.charAt(i)) >= 0) {
return true; // a vowel exists -> Alice wins
}
}
return false; // no vowels -> Bob wins
}bool doesAliceWin(string s) {
string vowels = "aeiou"; // the five English vowels
// Game theory result: with optimal play Alice loses
// only when the string has NO vowels at all. Otherwise
// she always wins, so we just look for one vowel.
for (char ch : s) {
if (vowels.find(ch) != string::npos) {
return true; // a vowel exists -> Alice wins
}
}
return false; // no vowels -> Bob wins
}Explanation
This problem looks like a hard adversarial search, but the optimal-play analysis collapses it to a single check: Alice wins if and only if the string contains at least one vowel.
Start with the easy facts. If the total number of vowels is odd, Alice simply removes the entire string in one move (an odd number of vowels is a legal move for her). The string is now empty, Bob has nothing to take, and Alice wins immediately.
If the total number of vowels is even and non-zero, Alice cannot grab everything at once, but she can play a setup move. She removes a substring that leaves behind an odd number of vowels — for instance she peels off characters so that exactly one fewer vowel remains. Whatever Bob does next (he must remove an even number of vowels, possibly zero consonants), the parity of remaining vowels stays odd on Alice's clock, and the count strictly shrinks each round. Alice can always answer, so Bob is the one who eventually runs out of moves.
If there are zero vowels, Alice is stuck on move one: every substring has an even (namely zero) vowel count, and she is only allowed odd counts. She cannot move at all, so she loses and the answer is false.
Combining the three cases, the only losing situation for Alice is a vowel-free string. So the whole algorithm is a linear scan: return true the moment we see a vowel, and false if we reach the end without one. No game tree, no recursion.
Example: s = "leetcoder" contains the vowels e, e, o, e, so the scan finds a vowel and returns true. By contrast s = "bbcd" has no vowels, so the scan finishes empty-handed and returns false.