# LeetCode 294: Flip Game II

## Problem Restatement

We are given a string `currentState` containing only:

```python
"+"
"-"
```

Two players take turns.

On each turn, a player chooses two consecutive plus signs:

```python
"++"
```

and flips them into:

```python
"--"
```

The player who cannot make a move loses.

We start first. We need to return whether the starting player can guarantee a win.

The source statement defines the game this way: players take turns flipping two consecutive `"++"` into `"--"`, and the game ends when a player can no longer move. The player unable to move loses.

## Input and Output

| Item | Meaning |
|---|---|
| Input | String `currentState` |
| Output | `True` if the starting player can force a win |
| Valid move | Replace one `"++"` with `"--"` |
| Losing state | No `"++"` remains |

Function shape:

```python
class Solution:
    def canWin(self, currentState: str) -> bool:
        ...
```

## Examples

For:

```python
currentState = "++++"
```

The starting player can win.

One winning move is to flip the middle pair:

```python
"++++" -> "+--+"
```

Now the other player has no `"++"` left, so they cannot move.

Return:

```python
True
```

For:

```python
currentState = "+"
```

There is no `"++"` pair.

The starting player cannot move.

Return:

```python
False
```

For:

```python
currentState = "++"
```

The starting player flips the only pair:

```python
"++" -> "--"
```

The other player cannot move.

Return:

```python
True
```

## First Thought: Try Every Move Recursively

This is a two-player game.

A position is winning if there exists at least one move that leaves the opponent in a losing position.

A position is losing if every possible move leaves the opponent in a winning position.

So we can recursively try every valid move.

```python
class Solution:
    def canWin(self, currentState: str) -> bool:
        for i in range(len(currentState) - 1):
            if currentState[i:i + 2] == "++":
                next_state = currentState[:i] + "--" + currentState[i + 2:]

                if not self.canWin(next_state):
                    return True

        return False
```

This is correct, but it recomputes the same states many times.

For example, flipping pair `A` then pair `B` can reach the same state as flipping pair `B` then pair `A`.

## Key Insight

Use memoization.

Store the result for each game state:

```python
state -> can current player force a win?
```

Then, before solving a state, check whether we already know the answer.

This turns repeated recursive work into a lookup.

The rule remains the same:

```python
current state is winning
if any next state is losing for the opponent
```

## Algorithm

Define a recursive function:

```python
dfs(state)
```

It returns whether the player to move can force a win from `state`.

For each index `i`:

1. If `state[i:i + 2] == "++"`, create the next state.
2. Recursively check whether the opponent can win from that next state.
3. If the opponent cannot win, return `True`.

If no move leads to an opponent loss, return `False`.

Memoize each result.

## Correctness

The game state fully determines whose position is winning or losing because both players have the same legal moves and the same objective.

If a state has no valid `"++"` move, the current player cannot move, so the state is losing. The algorithm returns `False` in this case.

If a state has at least one move to a losing state for the opponent, the current player can choose that move and force a win. The algorithm detects this by checking:

```python
if not dfs(next_state):
    return True
```

If every possible move leads to a winning state for the opponent, then no matter what the current player does, the opponent can force a win. The algorithm returns `False`.

The recursion tries every legal move, so it misses no winning move. Memoization only reuses previously computed correct results for identical states.

Therefore the algorithm returns `True` exactly when the starting player can guarantee a win.

## Complexity

Let:

```python
n = len(currentState)
```

| Metric | Value | Why |
|---|---|---|
| Time | Exponential | There can be exponentially many reachable game states |
| Space | Exponential | Memoization may store many states |

Each state scans the string to find valid moves.

Memoization greatly reduces repeated work, but the number of distinct states can still be exponential in the worst case.

## Implementation

```python
class Solution:
    def canWin(self, currentState: str) -> bool:
        memo = {}

        def dfs(state: str) -> bool:
            if state in memo:
                return memo[state]

            for i in range(len(state) - 1):
                if state[i:i + 2] == "++":
                    next_state = state[:i] + "--" + state[i + 2:]

                    if not dfs(next_state):
                        memo[state] = True
                        return True

            memo[state] = False
            return False

        return dfs(currentState)
```

## Code Explanation

We store solved states here:

```python
memo = {}
```

The recursive function answers whether the current player can win from `state`:

```python
def dfs(state: str) -> bool:
```

If we have already solved the state, we return the cached answer:

```python
if state in memo:
    return memo[state]
```

Then we scan every adjacent pair:

```python
for i in range(len(state) - 1):
```

A move is legal only when the pair is `"++"`:

```python
if state[i:i + 2] == "++":
```

We create the next state by flipping that pair:

```python
next_state = state[:i] + "--" + state[i + 2:]
```

If the opponent loses from that next state:

```python
if not dfs(next_state):
```

then the current state is winning.

If no winning move is found, this state is losing:

```python
memo[state] = False
return False
```

## Testing

```python
def test_can_win():
    s = Solution()

    assert s.canWin("++++") is True
    assert s.canWin("+") is False
    assert s.canWin("++") is True
    assert s.canWin("+++") is True
    assert s.canWin("+++++") is False
    assert s.canWin("+-++") is True
    assert s.canWin("--") is False

    print("all tests passed")

test_can_win()
```

Test meaning:

| Test | Why |
|---|---|
| `"++++"` | Standard winning example |
| `"+"` | No valid move |
| `"++"` | One move wins immediately |
| `"+++"` | Starting player can leave no move |
| `"+++++"` | Every move gives opponent a win |
| `"+-++"` | Only one separated valid pair |
| `"--"` | No plus pair exists |