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.

Description Hints 3 Solution Video 4:51

3227. Vowels Game in a String

Medium77.1% acceptance3 companies

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 s that contains an odd number of vowels.
On Bob's turn, he has to remove any non-empty substring from 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:

Alice plays first, she can delete the underlined substring in s = "leetcoder" which contains 3 vowels. The resulting string is s = "der".
Bob plays second, he can delete the underlined substring in s = "der" which contains 0 vowels. The resulting string is s = "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 <= 10⁵
s consists only of lowercase English letters.

Asked at 3 companies

Google Amazon Meta

Topics

Hints open one at a time

Hint 1

If there are no vowels in the initial string, then Bob wins.

Hint 2

If the number of vowels in the initial string is odd, then Alice can remove the whole string on her first turn and win.

Hint 3

What if the number of vowels in the initial string is even? What’s the optimal play for Alice’s first turn?

4:51

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def doesAliceWin(self, s: str) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

"leetcoder"

Input

"bbcd"

Your code is saved on this device.Solution