3227. Vowels Game In String

Problem Statement in English

Alice and Bob are playing a game with a string s.

In Alice’s turn she can remove any non empty substring of s that consists of an odd number of vowels. In Bob’s turn he can remove any non empty substring of s that consists of an even number of vowels. The players alternate turns, with Alice starting first.

If a player cannot make a move, they lose the game. Return true if Alice wins the game or false if Bob wins the game, assuming both players play optimally.

Approach

You have to realize that Alice can always win if there is at least one vowel in the string. This is because she can always remove that single vowel in her first turn, leaving Bob with no vowels to remove.

If there are an even number of vowels, Alice can take an odd number of them, leaving an odd number for Bob. Bob then takes an even number, leaving an odd number for Alice again. And in this turn Alice will win by taking all the remaining vowels.

If there are no vowels in the string, Alice cannot make a move and loses the game.

Solution in Python

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        vowels = list('aeiou')

        flag = False
        
        for c in s:
            if c in vowels:
                flag = True
                break

        return False if not flag else True

Complexity

• Time: $O(n)$
  Since we are iterating through the string once.

• Space: $O(1)$
  We are using a constant amount of space.

And we are done.