# Vowels Game in a String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/vowels-game-in-a-string)
Canonical: https://scaleengineer.com/dsa/problems/vowels-game-in-a-string
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Game Theory](https://scaleengineer.com/dsa/patterns/game-theory)
**Data structures:** String
---
## Problem
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.

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 <= 105`
* `s` consists only of lowercase English letters.

# Approaches
## Brute-force with Memoization
This approach models the game directly using recursion to explore the game tree. Each state in the game is represented by the current string. We determine if a player can win from a given state by checking if they can make a move to a state from which the other player is guaranteed to lose. Memoization is used to store the results for states that have already been computed, which is a standard technique for such game theory problems. However, the number of possible strings that can be generated is enormous, making this approach impractical for the given constraints.
**Time:** O(S * N^3), where S is the number of reachable string states. The N^3 factor comes from iterating through O(N^2) substrings and performing string operations. This is extremely slow. · **Space:** O(S * N), where S is the number of reachable string states and N is the max string length. This is prohibitively large.
**Pros:** Provides a general framework for solving impartial/partisan games.; Correctly solves the problem for very small input sizes.
**Cons:** Extremely inefficient in both time and space due to the vast number of possible string states.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core idea is to implement a function that simulates the game for a given player and string. Let's say we have a function `canAliceWin(String s)`. This function will try every possible move for Alice. A move for Alice is to remove a substring with an odd number of vowels. For each such move, a new string `s_next` is generated. Alice wins if she can find at least one move to `s_next` from which Bob cannot win. To check if Bob can win from `s_next`, we would need another function, `canBobWin(s_next)`, which would recursively check Bob's moves.

This mutual recursion can be simplified into a single function that takes the current string and the current player as arguments. We use a map to memoize the results for `(string, player)` pairs to avoid re-calculating the winner for the same game state.

Despite memoization, the state space is too large. The number of substrings of a string of length `N` is `O(N^2)`. Each removal creates a new string. The number of distinct strings that can be formed throughout the game can be exponential in the worst case, leading to prohibitive time and space complexity.

```java
// This is a conceptual illustration. A full implementation would be complex and inefficient.
class Solution {
    private Map<String, Boolean> memoAlice; // Memoization for Alice's turn
    private Map<String, Boolean> memoBob;   // Memoization for Bob's turn
    private Set<Character> vowels = new HashSet<>(Arrays.asList('a', 'e', 'i', 'o', 'u'));

    public boolean doesAliceWin(String s) {
        memoAlice = new HashMap<>();
        memoBob = new HashMap<>();
        return canAliceWin(s);
    }

    private boolean isVowel(char c) {
        return vowels.contains(c);
    }

    private int countVowels(String s) {
        int count = 0;
        for (char c : s.toCharArray()) {
            if (isVowel(c)) {
                count++;
            }
        }
        return count;
    }

    private boolean canAliceWin(String s) {
        if (memoAlice.containsKey(s)) return memoAlice.get(s);

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (countVowels(sub) % 2 != 0) { // Alice's move
                    String nextState = s.substring(0, i) + s.substring(j + 1);
                    if (!canBobWin(nextState)) {
                        memoAlice.put(s, true);
                        return true;
                    }
                }
            }
        }
        memoAlice.put(s, false);
        return false;
    }

    private boolean canBobWin(String s) {
        if (s.isEmpty()) return false;
        if (memoBob.containsKey(s)) return memoBob.get(s);

        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                String sub = s.substring(i, j + 1);
                if (countVowels(sub) % 2 == 0) { // Bob's move
                    String nextState = s.substring(0, i) + s.substring(j + 1);
                    if (!canAliceWin(nextState)) {
                        memoBob.put(s, true);
                        return true;
                    }
                }
            }
        }
        memoBob.put(s, false);
        return false;
    }
}
```
### Algorithm
- Define a recursive function, say `canWin(string s, player p)`, which returns `true` if the current player `p` can win with the string `s`.
- The function iterates through all possible moves for the current player. A move involves selecting a substring `sub` that satisfies the player's vowel count rule (odd for Alice, even for Bob) and removing it to form a new string `s'`.
- For each valid move leading to a new string `s'`, the function recursively calls `canWin(s', other_player)`.
- If any recursive call returns `false`, it means the current player has found a move that leads to a losing state for the opponent. Thus, the current player wins, and the function returns `true`.
- If all possible moves lead to winning states for the opponent (all recursive calls return `true`), the current player cannot force a win from the current state, so the function returns `false`.
- The base case for the recursion is when a player has no valid moves, in which case they lose, and the function returns `false`.
- To optimize, use memoization (a hash map) to store the results for each state `(s, p)` to avoid recomputing the outcome for the same string and player.

## Logical Deduction on Vowel Presence
A much more efficient approach comes from a logical deduction about the game's properties rather than simulating it. By analyzing the win/loss conditions and the effect of moves on the total vowel count, we can find a simple invariant that determines the winner. The key insight is that the game's outcome is solely determined by the presence of at least one vowel in the initial string.
**Time:** O(N), where N is the length of the string. In the best case, it's O(1) if a vowel is found at the beginning. In the worst case, we scan the entire string once. · **Space:** O(1), as we only need a constant amount of extra space for the set of vowels.
**Pros:** Extremely efficient with linear time complexity.; Very simple to implement.; Requires minimal space.
**Cons:** The correctness of this approach depends on a logical insight that might not be immediately apparent.
### Explanation
Let's analyze the game from a higher level. A player who can make a move to a state where the opponent is guaranteed to lose, wins. 

**Losing Conditions:**
- **Alice loses** if she cannot make a move. This happens if there are no substrings with an odd number of vowels. This is only true if the string has **no vowels at all**. If there's even one vowel `v`, Alice can remove the substring `"v"` (which has 1 vowel, an odd number) and make a valid move.
- **Bob loses** if he cannot make a move. This happens if there are no substrings with an even number of vowels. This is only true if the string is a **single vowel character** (e.g., `"a"`). Any other string either contains a consonant (which can be removed as a substring with 0 vowels) or is composed of multiple vowels (a substring of two vowels can be removed, having 2 vowels).

**Game Analysis:**
1.  **If the initial string `s` has no vowels:** Alice has no valid moves on her first turn. She loses immediately. The function should return `false`.

2.  **If the initial string `s` has at least one vowel:** Alice can always make a move. Let's see if she has a winning strategy.
    - **Optimal Play:** A player who receives a string whose total vowel count matches their move's parity requirement can win immediately by removing the entire string. Alice wins on receiving a string with an odd total vowel count. Bob wins on receiving one with an even total vowel count.
    - **Scenario A: `count_vowels(s)` is odd.** It's Alice's turn. The total vowel count is odd, which matches her rule. She can remove the entire string `s`. Bob is left with an empty string, has no moves, and loses. Alice wins.
    - **Scenario B: `count_vowels(s)` is even (and > 0).** It's Alice's turn. She cannot win in one move. She must remove a substring with an odd number of vowels. The remaining string `s'` will have a total vowel count of `even - odd = odd`. So, Alice will always leave Bob with a string that has an odd number of vowels.
    Now, it's Bob's turn with string `s'`. It has an odd number of vowels. This does not match his rule (even), so he cannot win immediately. He must remove a substring with an even number of vowels. The remaining string `s''` will have a total vowel count of `odd - even = odd`. Bob is forced to leave Alice with a string that has an odd number of vowels.
    Now, it's Alice's turn again. She receives `s''`, which has an odd number of vowels. As per Scenario A, she can remove the entire string and win.

**Conclusion:** Alice loses only if the string has zero vowels. If there is at least one vowel, she is guaranteed to have a winning strategy. Therefore, the problem simplifies to checking for the existence of any vowel in the string.

```java
class Solution {
    public boolean doesAliceWin(String s) {
        // The set of vowels for quick lookup.
        Set<Character> vowels = Set.of('a', 'e', 'i', 'o', 'u');
        
        // Iterate through the string to find at least one vowel.
        for (int i = 0; i < s.length(); i++) {
            if (vowels.contains(s.charAt(i))) {
                // If a vowel is found, Alice has a winning strategy.
                return true;
            }
        }
        
        // If no vowels are found after checking the whole string,
        // Alice cannot make a move and loses.
        return false;
    }
}
```
### Algorithm
- First, analyze the conditions under which a player loses. A player loses if they cannot make a valid move.
- Alice loses if she receives a string with no vowels, because any substring would have 0 (an even number of) vowels, and she needs to remove one with an odd number.
- Bob loses if he receives a string where every substring has an odd number of vowels. This only happens if the string is a single vowel character.
- If the initial string `s` has no vowels, Alice cannot make her first move and loses immediately.
- If `s` has at least one vowel, Alice can always make a move (e.g., by removing a single vowel). So she won't lose on her first turn.
- Consider the total number of vowels. If a player receives a string where the total vowel count matches their rule (odd for Alice, even for Bob), they can remove the entire string and win.
- If the initial vowel count is odd, Alice removes the whole string and wins.
- If the initial vowel count is even and positive, Alice must remove a substring with an odd number of vowels. This leaves a string with `even - odd = odd` vowels for Bob.
- Bob now has a string with an odd number of vowels. He must remove a substring with an even number of vowels. This leaves a string with `odd - even = odd` vowels for Alice.
- Alice will then receive a string with an odd number of vowels, at which point she can remove the entire string and win.
- Therefore, Alice only loses if the string has no vowels to begin with. Otherwise, she always has a winning strategy.
- The final algorithm is to simply check if the string contains at least one vowel.

# Solutions
### Java

```java
class Solution {
public
  boolean doesAliceWin(String s) {
    for (int i = 0; i < s.length(); ++i) {
      if ("aeiou".indexOf(s.charAt(i)) != -1) {
        return true;
      }
    }
    return false;
  }
}

```

### CPP

```cpp
class Solution { public: bool doesAliceWin ( string s ) { string vowels = "aeiou" ; for ( char c : s ) { if ( vowels . find ( c ) != string :: npos ) { return true ; } } return false ; } };
```

### Python

```python
class Solution : def doesAliceWin ( self , s : str ) -> bool : vowels = set ( "aeiou" ) return any ( c in vowels for c in s )
```