Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Only the presence of a vowel matters. Without any vowels, Alice has no legal first move. With an odd number of vowels, she can remove the entire string immediately. With a positive even number, she can first remove a substring containing an odd number of vowels, leaving an odd total.

Approach

Scan the string and return true as soon as a character belongs to aeiou; return false if none does.

For the positive-even case, Alice can remove just one vowel. Bob must then remove an even number of vowels, so the remaining total stays odd and cannot become zero. If Bob can move, Alice removes the entire remaining string on her next turn; if he cannot, she has already won. This proves that finding any vowel is sufficient, without simulating moves or counting the exact total.

class Solution:
    def doesAliceWin(self, s: str) -> bool:
        for x in s:
            if x in 'aeiou':
                return True

        return False

Complexity analysis

Let n = s.length. Time: O(n). Auxiliary space: O(1).