Vowels Game in a String

For this question, realise that a string can have:

• zero vowels
  • Bob would always win as Alice cannot make her move
• an odd number of vowels
  • Alice can always win as she would erase the entire string, making it impossible for Bob to make a move
• an even number of vowels (non-zero)
  • Alice can always win
  • if there are n vowels in the string
    • since n is even, Alice can erase n-1 vowels to leave 1 vowel
    • then, Bob either loses (no consonants to erase) or erases consonants
    • afterwards, Alice can erase all the leftover letters (including the 1 vowel), meaning Bob will always consequently lose

Therefore, we can just define a function to return if a character is a vowel:

bool isVowel(char c) {
    return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
}

Finally, we can iterate through the string and return a Bob win if and only if there are zero vowels in the string. Otherwise, we can return an Alice win.

bool doesAliceWin(string s) {
    int count = 0;
    for (char& c : s) {
        if(isVowel(c)) {
            ++count;
        }
    }

    return count == 0 ? false : true;
}

code

class Solution {
public:
    bool doesAliceWin(string s) {
        int count = 0;
        for (char& c : s) {
            if(isVowel(c)) {
                ++count;
            }
        }

        return count == 0 ? false : true;
    }
private:
    bool isVowel(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u';
    }
};

complexity

• Time: O(n) where n denotes the number of letters inside s
• Space: O(1)

time taken

• 2 minutes and 5 seconds