We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Vowels Game in a String

Number: 3462

Difficulty: Medium

Paid? No

Companies: N/A

Problem Description

Alice and Bob play a game on a string s. In each turn, a player removes a non-empty substring from s with a specific condition: Alice (who goes first) must remove a substring containing an odd number of vowels, whereas Bob must remove one with an even number. The game continues until a player cannot make a move, who then loses. Determine if Alice can win the game assuming both play optimally.

Key Insights

  • The outcome hinges on the parity (odd or even) of the total number of vowels in the string.
  • Alice’s move requires an odd count of vowels; Bob’s requires an even count.
  • If the total number of vowels is odd, Alice can force a win; if even, she will lose.
  • This reduces the problem to simply counting vowels in the string and checking their parity.

Space and Time Complexity

Time Complexity: O(n), where n is the length of s (one pass to count vowels).
Space Complexity: O(1) (only a few counter variables are used).

Solution

The problem is distilled to computing the total vowel count in the string s. With optimal play, the player who can control the parity of the vowels will force a win. Specifically, if the total count of vowels is odd, Alice wins; if even, Bob wins. Our approach is to traverse the string once, count the vowels, and then return true if the count is odd.

Code Solutions

# Python solution for the Vowels Game in a String problem
# Count the vowels in the string and check if the total is odd

def vowels_game(s: str) -> bool:
    # Define the set of vowels for quick lookup
    vowels = {'a', 'e', 'i', 'o', 'u'}
    
    total_vowels = 0
    # Count vowels in the string
    for char in s:
        if char in vowels:
            total_vowels += 1
            
    # Alice wins if total vowels is odd
    return total_vowels % 2 == 1

# Example usage:
# print(vowels_game("leetcoder"))  # True
# print(vowels_game("bbcd"))       # False
← Back to All Questions