main.cpp

// Source: https://leetcode.com/problems/vowels-game-in-a-string
// Title: Vowels Game in a String
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// Alice and Bob are playing a game on a string.
//
// You are given a string `s`, Alice and Bob will take turns playing the following game where Alice starts **first**:
//
// - On Alice's turn, she has to remove any **non-empty substring** from `s` that contains an **odd** number of vowels.
// - On Bob's turn, he has to remove any **non-empty substring** from `s` that contains an **even** number of vowels.
//
// A **substring** is a contiguous sequence of characters within a string.
//
// The first player who cannot make a move on their turn loses the game. We assume that both Alice and Bob play **optimally**.
//
// Return `true` if Alice wins the game, and `false` otherwise.
//
// The English vowels are: `a`, `e`, `i`, `o`, and `u`.
//
// **Example 1:**
//
// ```
// Input: s = "leetcoder"
// Output: true
// Explanation:
// Alice can win the game as follows:
// - Alice plays first, she can delete the underlined substring in `s = "**leetco**der"` which contains 3 vowels. The resulting string is `s = "der"`.
// - Bob plays second, he can delete the underlined substring in `s = "**d**er"` which contains 0 vowels. The resulting string is `s = "er"`.
// - Alice plays third, she can delete the whole string `s = "**er**"` which contains 1 vowel.
// - Bob plays fourth, since the string is empty, there is no valid play for Bob. So Alice wins the game.
// ```
//
// **Example 2:**
//
// ```
// Input: s = "bbcd"
// Output: false
// Explanation:
// There is no valid play for Alice in her first turn, so Alice loses the game.
// ```
//
// **Constraints:**
//
// - `1 <= s.length <= 10^5`
// - `s` consists only of lowercase English letters.
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

#include <string>

using namespace std;

// Math
//
// If there is no vowel, then Alice loses since she can't move.
//
// If there are odd vowels, then Alice wins.
// She can remove the whole string, and then Bob can't move.
//
// If there are even vowels, then Alice wins.
// After she removing any substring, there will be odd vowels.
// No matter what Bob does, there will still be odd vowels.
// Alice can remove the whole string, and then Bob can't move.
class Solution {
 public:
  bool doesAliceWin(string s) {
    auto check = [](char c) -> bool { return c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u'; };
    return any_of(s.cbegin(), s.cend(), check);
  }
};