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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Vowels Game in a String

Difficulty: Medium

Problem Description

Alice and Bob are playing a game on a string. Given a string s, Alice and Bob will take turns removing non-empty substrings containing an odd or even number of vowels, respectively. Alice starts first. The first player who cannot make a move loses the game. Return true if Alice wins the game, and false otherwise.

Key Insights

  • Alice can only remove substrings containing an odd number of vowels.
  • Bob can only remove substrings containing an even number of vowels.
  • The game ends when a player cannot make a valid move.
  • Both players are assumed to play optimally, meaning they will make moves that maximize their chances of winning.
  • The total count of vowels in the string will heavily influence the outcome of the game.

Space and Time Complexity

Time Complexity: O(n), where n is the length of the string. This is because we may need to traverse the string to count vowels. Space Complexity: O(1), as we are using a fixed amount of space for counters.

Solution

To determine if Alice wins, we can count the total number of vowels in the string. If the count of vowels is odd, Alice can make a valid move in her first turn, and she will win. If the count is even, she cannot make a valid move, and thus Bob will win. Therefore, the solution hinges on counting the vowels and checking their parity.

Code Solutions

def vowelsGame(s: str) -> bool:
    vowels = set('aeiou')
    count = sum(1 for char in s if char in vowels)
    return count % 2 == 1  # Alice wins if the count of vowels is odd
← Back to All Questions