Vowels Game in a String - Solution & Explanation
Problem Statement
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.
The solution involves counting the number of vowels in the string. If the total number of vowels is odd, Alice has a winning strategy because she can leave Bob with an even number of vowels after each of her moves. If it's even, Bob has a winning strategy.
Complexity
Time Complexity: O(n), where n is the length of the string, as we traverse the string once to count vowels.
Space Complexity: O(1), because no extra space is used relative to input size.
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.
Using DP logic disjunctively and flipping states via bitwise or structured assignments, this solution approaches determining parity transition and valid play states.
Complexity
Time Complexity: O(n) traversal by characters.
Space Complexity: O(1), with minor fixed supplementary data.
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).
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Game Theory with Vowel Parity Calculation | Time Complexity: O(n), where n is the length of the string, as we traverse the string once to count vowels. |
| Approach 2: Dynamic Programming Perspective | Time Complexity: O(n) traversal by characters. |
| Brain Teaser | — |
Detailed 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 |
Video Solution
3227. Vowels Game in a String | Greedy | Strings • Aryan Mittal • 7,284 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Vowels Game in a String easy or hard?
Vowels Game in a String Python/Java solution
How to solve Vowels Game in a String in O(n)?
What is the best approach for Vowels Game in a String?
Is Vowels Game in a String asked at Google/Amazon/Meta?
What data structure is used in Vowels Game in a String?
What is the time complexity of Vowels Game in a String?
Ready to solve this problem?
Practice Vowels Game in a String with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor