# LeetCode 293: Flip Game

## Problem Restatement

We are given a string `currentState` containing only two characters:

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

A valid move means choosing two consecutive plus signs:

```python
"++"
```

and flipping them into:

```python
"--"
```

We need to return all possible states of the string after making exactly one valid move.

The answer may be returned in any order. If there is no valid move, return an empty list. The source statement defines the game this way: players take turns flipping two consecutive `"++"` into `"--"`, and this problem asks only for all states after one valid move.

## Input and Output

| Item | Meaning |
|---|---|
| Input | A string `currentState` |
| Output | A list of strings |
| Valid move | Flip one occurrence of `"++"` into `"--"` |
| Characters | Only `'+'` and `'-'` |
| Order | Any output order is accepted |

Function shape:

```python
class Solution:
    def generatePossibleNextMoves(self, currentState: str) -> list[str]:
        ...
```

## Examples

For:

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

There are three valid pairs:

| Flipped Index Pair | Result |
|---|---|
| `(0, 1)` | `"--++"` |
| `(1, 2)` | `"+--+"` |
| `(2, 3)` | `"++--"` |

So the answer is:

```python
["--++", "+--+", "++--"]
```

For:

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

There is no consecutive `"++"` pair.

So the answer is:

```python
[]
```

For:

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

There are two valid moves:

```python
"-- --++"  # flipping the first pair, written without spaces: "----++"
"++ ----"  # flipping the last pair, written without spaces: "++----"
```

So the answer is:

```python
["----++", "++----"]
```

## First Thought: Simulate Every Legal Move

The problem only asks for the result after one move.

So we do not need game theory, recursion, or minimax.

We only need to scan each adjacent pair of characters.

Whenever we find:

```python
currentState[i] == "+"
currentState[i + 1] == "+"
```

we create a new string where those two positions become `"-"`.

## Key Insight

Each valid move is independent.

For every index `i`, if the substring starting at `i` is:

```python
"++"
```

then one valid next state is:

```python
currentState[:i] + "--" + currentState[i + 2:]
```

This keeps everything before the pair unchanged, replaces the pair with `"--"`, and keeps everything after the pair unchanged.

## Algorithm

Initialize an empty list:

```python
result = []
```

Scan every possible adjacent pair:

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

If the pair at `i` and `i + 1` is `"++"`, build the next state:

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

Append it to `result`.

After the loop, return `result`.

## Correctness

Every valid move flips exactly one adjacent `"++"` pair into `"--"`.

The algorithm checks every adjacent pair in the string. Therefore, every possible location for a valid move is considered.

When the algorithm finds a pair equal to `"++"`, it constructs the exact state produced by flipping that pair and leaving all other characters unchanged. So every generated state is valid.

If a pair is not `"++"`, no valid move can be made at that position, so skipping it is correct.

Since all adjacent pairs are checked, no valid move is missed. Therefore the returned list contains exactly all possible next states after one valid move.

## Complexity

Let:

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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n^2)` | We scan `n` positions, and each generated string copy costs `O(n)` |
| Space | `O(n^2)` | In the worst case, there are `O(n)` output strings, each of length `n` |

If we ignore the size of the returned output, the extra working space is `O(1)`.

## Implementation

```python
class Solution:
    def generatePossibleNextMoves(self, currentState: str) -> list[str]:
        result = []

        for i in range(len(currentState) - 1):
            if currentState[i] == "+" and currentState[i + 1] == "+":
                next_state = currentState[:i] + "--" + currentState[i + 2:]
                result.append(next_state)

        return result
```

## Code Explanation

We store all generated states here:

```python
result = []
```

Then we scan adjacent pairs:

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

The last possible pair starts at `len(currentState) - 2`, so this range is correct.

A move is valid only when both characters are plus signs:

```python
if currentState[i] == "+" and currentState[i + 1] == "+":
```

The new state is built by replacing only that pair:

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

Then we add it to the answer:

```python
result.append(next_state)
```

Finally:

```python
return result
```

returns all possible next states.

## Testing

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

    assert sorted(s.generatePossibleNextMoves("++++")) == sorted([
        "--++",
        "+--+",
        "++--",
    ])

    assert s.generatePossibleNextMoves("+-+") == []

    assert sorted(s.generatePossibleNextMoves("++--++")) == sorted([
        "----++",
        "++----",
    ])

    assert s.generatePossibleNextMoves("--") == []

    assert s.generatePossibleNextMoves("++") == ["--"]

    print("all tests passed")

test_generate_possible_next_moves()
```

Test meaning:

| Test | Why |
|---|---|
| `"++++"` | Multiple overlapping valid pairs |
| `"+-+"` | No valid move |
| `"++--++"` | Two separated valid pairs |
| `"--"` | Only minus signs |
| `"++"` | Smallest string with one valid move |