#3227

Medium

LeetCode Problem Workspace

Vowels Game in a String

Solve the Vowels Game in a String using optimal moves and string analysis to predict the winner efficiently and accurately.

math string brainteaser game theory

Problem Statement

Alice and Bob play a game on a given lowercase string s. They take turns removing vowels, and the first player unable to move loses. Both players play optimally.

You must determine whether Alice can guarantee a win given the starting string. Consider the positions of vowels, potential moves, and the total length of s to decide the winner efficiently.

Examples

Example 1

Input: s = "leetcoder"

Output: true

Alice can win the game as follows:

Example 2

Input: s = "bbcd"

Output: false

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.

Solution Approach

Count Vowels Efficiently

Iterate through the string s and count all vowels. This helps determine the number of potential moves and establishes if Alice has any first-move options.

Apply Turn-Based Logic

Use the total vowel count to simulate optimal moves: if the count is zero at Alice's first turn, Bob wins. Otherwise, alternate turns until one player cannot move, applying math to skip unnecessary simulations.

Return Winner

Based on the analysis, return true if Alice can force a win and false if Bob will win. This ensures a direct, efficient solution without iterating through all game states.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on traversing the string once to count vowels, giving O(n). Space complexity is O(1) since only counters are needed.

What Interviewers Usually Probe

Check if the candidate identifies counting vowels as the key first step.
Observe if the candidate considers the failure mode when the string has no vowels.
Look for recognition that optimal play can be predicted using simple math rather than full simulation.

Common Pitfalls or Variants

Common pitfalls

Failing to check if the initial string has zero vowels, leading to incorrect winner prediction.
Overcomplicating the game simulation instead of using vowel count and turn logic.
Ignoring edge cases with single-character strings or strings with all consonants.

Follow-up variants

Change the winning condition to removing consonants instead of vowels and analyze the impact on optimal strategy.
Use a string with alternating vowels and consonants to see how move sequences affect the winner.
Introduce a rule limiting moves per turn to 2 vowels, requiring adjusted math for optimal play.

FAQ

What is the main strategy to win the Vowels Game in a String?

Count vowels and apply turn-based logic; Alice wins if she has a first-move advantage and Bob wins otherwise.

How does the math plus string pattern apply here?

Vowel counting is the math part, string traversal is the string part, and combining them predicts the winner efficiently.

What should I do if the string has no vowels?

Alice cannot move, so Bob wins immediately. This edge case is critical for correct results.

Can this approach handle very long strings?

Yes, because counting vowels requires a single pass with O(n) time and O(1) space.

Are there variations of this game that change the optimal strategy?

Yes, altering the type of removable characters or limiting moves per turn changes the math calculation for winning.

terminal

Solution

Solution 1: Brain Teaser

Let's denote the number of vowels in the string as $k$.

1

2

3

4

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        vowels = set("aeiou")
        return any(c in vowels for c in s)

Continue Practicing

#3222 find the winning player in coin game #3260 find the largest palindrome divisible by k #3274 check if two chessboard squares have the same color