LeetCode 3227 - Vowels Game in a String

LeetCode Problem 3227

Difficulty: 🟡 Medium
Topics: Math, String, Brainteaser, Game Theory

Solution

Problem Understanding

The problem describes a two-player game between Alice and Bob played on a string s. Alice always moves first. The rules for each player are based on vowel counts in substrings: Alice can remove any non-empty substring containing an odd number of vowels, while Bob can remove any non-empty substring containing an even number of vowels. The game ends when a player cannot make a move on their turn, and that player loses. The task is to determine whether Alice can guarantee a win if both play optimally.

The input is a lowercase string of English letters, with a length between 1 and 100,000. The output is a boolean, true if Alice wins and false otherwise. The problem is constrained by string length, meaning any brute-force approach that explores all possible substring removals will be too slow.

Important edge cases include strings with no vowels, strings with only vowels, and very short strings of length 1. These cases can affect the initial move availability and therefore the outcome.

Approaches

The brute-force approach would involve simulating all possible moves for both players recursively. For Alice's turn, you would generate every non-empty substring containing an odd number of vowels, remove it, and recursively check if Bob can win. On Bob's turn, the same logic applies for even vowel substrings. This approach is guaranteed to work but is exponentially slow because the number of substrings grows as O(n²) and the recursion explores all game states.

The key insight for an optimal solution comes from observing the parity of vowels. Alice can only remove substrings with an odd number of vowels, and Bob can only remove substrings with an even number of vowels. If the total number of vowels in the string is odd, Alice can remove the whole string immediately and win. If the total number of vowels is even, Alice has no winning move from the start because Bob will always be able to respond and maintain the parity advantage. Essentially, the game reduces to counting the vowels and checking their parity.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n²)	Recursive simulation of all substrings; infeasible for large n
Optimal	O(n)	O(1)	Count vowels and use parity reasoning; immediate solution

Algorithm Walkthrough

1. Initialize a set of vowels {'a', 'e', 'i', 'o', 'u'} to quickly check if a character is a vowel.
2. Iterate through the string and count the total number of vowels.
3. If the total number of vowels is odd, return true because Alice can remove a substring with all vowels and win immediately.
4. If the total number of vowels is even, return false because Alice has no winning move, and Bob can always maintain control.

Why it works: The invariant here is the parity of the number of vowels in the string. Alice can only remove odd-vowel substrings, so if the initial count is odd, she can take the entire string. If the initial count is even, Alice cannot remove a substring that leaves Bob with an odd count in his turn. Since both play optimally, the parity dictates the winner.

Python Solution

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        vowels = {'a', 'e', 'i', 'o', 'u'}
        vowel_count = sum(1 for char in s if char in vowels)
        return vowel_count % 2 == 1

The code initializes a set of vowels for fast membership checking. It then iterates through the string and counts how many characters are vowels. The parity of the total count determines if Alice can win immediately. If the count is odd, Alice wins; if it is even, she loses.

Go Solution

func doesAliceWin(s string) bool {
    vowels := map[rune]bool{'a': true, 'e': true, 'i': true, 'o': true, 'u': true}
    count := 0
    for _, ch := range s {
        if vowels[ch] {
            count++
        }
    }
    return count%2 == 1
}

In Go, we use a map for vowel lookup and a loop over the string using range to count vowels. The parity check is the same: if the total count is odd, Alice wins.

Worked Examples

Example 1: s = "leetcoder"

Step	Description	Vowel Count	Result
Initial	Count vowels in "leetcoder"	5	5 % 2 = 1, odd
Alice's turn	Alice removes the entire substring with vowels	-	Alice wins

Example 2: s = "bbcd"

Step	Description	Vowel Count	Result
Initial	Count vowels in "bbcd"	0	0 % 2 = 0, even
Alice's turn	No odd-vowel substring exists	-	Alice loses

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	We iterate through the string once to count vowels
Space	O(1)	Only a fixed set/map and counter are used

The algorithm is efficient because it only needs a single pass over the string and uses constant additional space.

Test Cases

# test cases
assert Solution().doesAliceWin("leetcoder") == True  # odd vowels, Alice wins
assert Solution().doesAliceWin("bbcd") == False      # no vowels, Alice loses
assert Solution().doesAliceWin("a") == True          # single vowel, Alice wins
assert Solution().doesAliceWin("b") == False         # single consonant, Alice loses
assert Solution().doesAliceWin("aeiou") == True      # all vowels, odd number, Alice wins
assert Solution().doesAliceWin("bcdfg") == False    # all consonants, Alice loses
assert Solution().doesAliceWin("leetcode") == False  # even vowels, Alice loses

Test	Why
"leetcoder"	Odd vowels, Alice should win
"bbcd"	No vowels, Alice cannot move, loses
"a"	Single vowel, Alice wins immediately
"b"	Single consonant, Alice loses
"aeiou"	Odd number of vowels, Alice wins
"bcdfg"	All consonants, Alice cannot move
"leetcode"	Even number of vowels, Alice loses

Edge Cases

One edge case is a string with no vowels. In this situation, Alice cannot make any move on her first turn, so she immediately loses. Another important edge case is a string consisting entirely of vowels with an odd length. Alice can remove the entire string in her first move and guarantee a win. A third edge case is a string of length one. If it is a vowel, Alice wins; if it is a consonant, she loses. Our implementation handles all these correctly by counting vowels and checking parity, which generalizes to all string lengths and compositions.