Vowels Game in a String solution and explanation
Google
9 more videos on this problem
3227. Vowels Game in a String | Greedy | StringsAryan Mittal · 4:51 · 7K views
Vowels Game in a String | Leetcode 3227Techdose · 6:58 · 1K views
3227. Vowels Game in a String | Leetcode Daily - PythonLeetcode Daily · 5:34 · 712 views
3227. Vowels Game in a String (Leetcode Medium)Programming Live with Larry · 7:25 · 412 views
Daily Leetcode #1991: Sep 12, 2025 - 3227. Vowels Game in a StringProgramming Live with Larry · 7:46 · 388 views
Vowels Game in a String | LeetCode 3227 | Best Solution ExplainedSanyam IIT Guwahati · 7:30 · 285 views
Vowels Game in a String | LeetCode 3227 - Pythonimpoldev · 4:50 · 146 views
Vowels Game in a String | LeetCode 3227 | Game TheoryCode Harmony · 13:31 · 134 views
3227 Vowels Game in a String | Leetcode | Java | Easy SolutionV-Solve · 6:38 · 98 views
Vowels Game in a String | Leetcode 3227 | Simple Explanation & SolutionExpertFunda · 13:10 · 68 views
The problem
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
sthat contains an odd number of vowels. - On Bob's turn, he has to remove any non-empty substring from
sthat 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 <= 105sconsists only of lowercase English letters.
Approach overview
Problem Overview: You are given a string and two players playing a game by removing substrings under specific vowel constraints. The task is to determine whether the first player (Alice) wins assuming both players play optimally.
Approach 1: Game Theory with Vowel Parity Calculation (O(n) time, O(1) space)
The key observation is that every valid move depends only on the number of vowels remaining in the string. Instead of simulating substring removals, count how many vowels exist using a single pass through the string. If the string contains at least one vowel, Alice can always make the first valid move and control the parity of the remaining vowels. Game theory analysis shows that any non‑zero vowel count leads to a winning position for the first player. Implementation is straightforward: iterate through the string, count characters in {a,e,i,o,u}, and return true if the count is greater than zero. This approach leverages insights from game theory and basic string traversal.
Approach 2: Dynamic Programming Perspective (O(n^2) time, O(n) space)
A more theoretical way to view the game is through state transitions based on the remaining substring. Define a DP state representing whether the current player can win given a substring with a certain number of vowels. For each state, try removing substrings that satisfy the vowel rule and check whether the opponent is forced into a losing state. This mirrors classic impartial games studied in mathematical game analysis. Although DP works conceptually, it becomes inefficient because there are many possible substrings to consider. After analyzing state transitions, the DP collapses into a much simpler rule: positions with zero vowels are losing states, and any position with at least one vowel is winning.
Recommended for interviews: The game‑theory observation with a single vowel count is what interviewers expect. It reduces a seemingly complex substring game into a simple invariant. Showing the DP reasoning first demonstrates understanding of state transitions, but recognizing the parity shortcut and reducing the solution to an O(n) scan demonstrates strong problem‑solving maturity.
Approach 1: Approach 1: Game Theory with Vowel Parity Calculation
The essence of this approach is to utilize game theory. The game can be represented as a state space where we keep track of the parity (odd/even) of the number of vowels at each point. Alice can remove a substring that has an odd number of vowels, while Bob can remove one with an even number of vowels.
We can maintain a rolling tally of the vowel count as we progress character by character through the string. The winning strategy boils down to ensuring that after each move, the opposing player is left at a disadvantageous state where they have no valid moves.
def alice_wins(s):
vowels = 'aeiou'
count_vowels = sum(1 for char in s if char in vowels)
return count_vowels % 2 != 0
s = "leetcoder"
print(alice_wins(s))public class Main {
public static void main(String[] args) {
String s = "leetcoder";
System.out.println(aliceWins(s));
}
public static boolean aliceWins(String s) {
int countVowels = 0;
for (char c : s.toCharArray()) {
if (isVowel(c)) {
countVowels++;
}
}
return countVowels % 2 != 0;
}
private static boolean isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
}#include <iostream>
#include <string>
using namespace std;
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
bool aliceWins(string s) {
int countVowels = 0;
for (char c : s) {
if (isVowel(c)) {
countVowels++;
}
}
return countVowels % 2 != 0;
}
int main() {
string s = "leetcoder";
cout << (aliceWins(s) ? "true" : "false") << endl;
return 0;
}function aliceWins(s) {
let countVowels = 0;
for (let char of s) {
if ('aeiou'.includes(char)) {
countVowels++;
}
}
return countVowels % 2 !== 0;
}
const s = "leetcoder";
console.log(aliceWins(s));#include <stdio.h>
#include <stdbool.h>
bool isVowel(char c) {
return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}
bool aliceWins(char* s) {
int countVowels = 0;
for (int i = 0; s[i] != '\0'; i++) {
if (isVowel(s[i])) {
countVowels++;
}
}
// If there is an odd number of vowels, Alice can win by always leaving Bob with an even count.
return countVowels % 2 != 0;
}
int main() {
char str[] = "leetcoder";
printf("%s\n", aliceWins(str) ? "true" : "false");
return 0;
}using System;
public class Program {
public static void Main() {
string s = "leetcoder";
Console.WriteLine(AliceWins(s) ? "true" : "false");
}
public static bool AliceWins(string s) {
int countVowels = 0;
foreach (char c in s) {
if (IsVowel(c)) {
countVowels++;
}
}
return countVowels % 2 != 0;
}
private static bool IsVowel(char c) {
return "aeiou".Contains(c);
}
}Using a list comprehension to quickly count vowels, this Python function makes a simple modulus check to determine if Alice can force a win.
Time Complexity: O(n) for counting vowels.
Space Complexity: O(1), aside from input storage.
Approach 2: Approach 2: Dynamic Programming Perspective
This alternative approach interprets the problem as a dynamic decision process, though complexity constraints prevent intensive use of dynamic programming arrays due to potential O(n^2) behavior.
Instead, it uses a form of strategic analysis focusing on transition states (substrings leading to even to odd swaps and vice versa). The player's turn depends on strategic positioning in terms of subarray boundaries and contributes to understanding how a dynamic programming table might be indirectly simulated or streamlined.
def pretty_imbalanced(s):
dp = [False, True]
count_vowels = 0
for c in s:
if c in 'aeiou':
count_vowels += 1
dp[count_vowels % 2] = not dp[count_vowels % 2]
return dp[0]
s = "leetcoder"
print(pretty_imbalanced(s))public class Main {
public static void main(String[] args) {
String s = "leetcoder";
System.out.println(prettyImbalanced(s));
}
public static boolean prettyImbalanced(String s) {
boolean[] dp = {false, true};
int vowelCount = 0;
for (char c : s.toCharArray()) {
if (isVowel(c)) {
vowelCount++;
}
dp[vowelCount % 2] = !dp[vowelCount % 2];
}
return dp[0];
}
private static boolean isVowel(char c) {
return "aeiou".indexOf(c) != -1;
}
}#include <iostream>
#include <string>
using namespace std;
bool prettyImbalanced(string s) {
bool dp[2] = {false};
dp[1] = true;
int vowelCount = 0;
for (char& c : s) {
if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
vowelCount++;
}
dp[vowelCount % 2] = !dp[vowelCount % 2];
}
return dp[0];
}
int main() {
string s = "leetcoder";
cout << (prettyImbalanced(s) ? "true" : "false") << endl;
return 0;
}function prettyImbalanced(s) {
let dp = [false, true];
let countVowels = 0;
for (let char of s) {
if ('aeiou'.includes(char)) {
countVowels++;
}
dp[countVowels % 2] = !dp[countVowels % 2];
}
return dp[0];
}
const s = "leetcoder";
console.log(prettyImbalanced(s));#include <stdio.h>
#include <stdbool.h>
bool prettyImbalanced(char* s) {
bool dp[2] = {false};
dp[1] = true;
int vowelCount = 0;
for (int i = 0; s[i]; ++i) {
if (s[i] == 'a' || s[i] == 'e' || s[i] == 'i' || s[i] == 'o' || s[i] == 'u') {
vowelCount++;
}
dp[vowelCount % 2] = !dp[vowelCount % 2];
}
return dp[0];
}
int main() {
char str[] = "leetcoder";
printf("%s\n", prettyImbalanced(str) ? "true" : "false");
return 0;
}using System;
public class Program {
public static void Main() {
string s = "leetcoder";
Console.WriteLine(PrettyImbalanced(s) ? "true" : "false");
}
public static bool PrettyImbalanced(string s) {
bool[] dp = new bool[] { false, true };
int vowelCount = 0;
foreach (char c in s) {
if (IsVowel(c)) {
vowelCount++;
}
dp[vowelCount % 2] = !dp[vowelCount % 2];
}
return dp[0];
}
private static bool IsVowel(char c) {
return "aeiou".IndexOf(c) >= 0;
}
}Transcending traditional DP, this Python code relies on concise logical tracking of in-play states. It systematically flips available plays, mapping optimal players' moves by zeroing in on balance status.
Time Complexity: O(n) for parsing and logical state checks.
Space Complexity: O(1), leveraging memory efficiency.
Approach 3: 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).
function doesAliceWin(s: string): boolean {
const vowels = 'aeiou';
for (const c of s) {
if (vowels.includes(c)) {
return true;
}
}
return false;
}func doesAliceWin(s string) bool {
vowels := "aeiou"
for _, c := range s {
if strings.ContainsRune(vowels, c) {
return true
}
}
return false
}impl Solution {
pub fn does_alice_win(s: String) -> bool {
let vowels = "aeiou";
for c in s.chars() {
if vowels.contains(c) {
return true;
}
}
false
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Game Theory with Vowel Parity Calculation | Time Complexity: O(n) for counting vowels. |
| Approach 2: Dynamic Programming Perspective | Time Complexity: O(n) for parsing and logical state checks. |
| Brain Teaser | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Game Theory with Vowel Counting | O(n) | O(1) | Best practical solution; simple scan determines the winner |
| Dynamic Programming Game States | O(n^2) | O(n) | Useful for reasoning about game states or explaining the winning invariant |
Frequently asked questions
Is Vowels Game in a String easy or hard?
The problem is labeled Medium because the statement suggests a complex substring game. Once the key insight about vowel count and winning states is discovered, the implementation becomes extremely simple with a linear scan.
Vowels Game in a String Python/Java solution
The implementation in Python or Java typically counts vowels using a loop and a set or conditional checks. After counting, return true if the count is greater than zero, otherwise false. The same logic translates directly to C++, C#, and JavaScript.
How to solve Vowels Game in a String in O(n)?
Iterate through the string and count vowels such as a, e, i, o, and u. If the total number of vowels is zero, Alice has no valid move and loses. If at least one vowel exists, Alice can always force a winning position. This reduces the entire game to a single linear pass.
What is the best approach for Vowels Game in a String?
The optimal approach uses game theory with a simple vowel count. Scan the string once and count how many vowels appear. If the count is greater than zero, Alice can always make a winning move. This results in O(n) time and O(1) space complexity.
Is Vowels Game in a String asked at Google/Amazon/Meta?
Problems involving string manipulation and game theory frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that require identifying winning states, parity rules, or optimal strategies are common in technical screening rounds.
What data structure is used in Vowels Game in a String?
No complex data structure is required for the optimal solution. A simple counter and a constant lookup for vowel characters are enough. The algorithm mainly relies on string traversal and a game‑theory observation.
What is the time complexity of Vowels Game in a String?
The optimal solution runs in O(n) time because the string is scanned once to count vowels. Only a few variables are used, so the space complexity is O(1). A theoretical dynamic programming interpretation could take O(n^2) time due to substring state exploration.