Watch 10 video solutions for Vowels Game in a String, a medium level problem involving Math, String, Brainteaser. This walkthrough by Aryan Mittal has 7,269 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
s that contains an odd number of vowels.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:
s = "leetcoder" which contains 3 vowels. The resulting string is s = "der".s = "der" which contains 0 vowels. The resulting string is s = "er".s = "er" which contains 1 vowel.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 <= 105s consists only of lowercase English letters.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 | 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 |