LeetCode 293: Flip Game

Problem Restatement

We are given a string currentState containing only two characters:

"+"
"-"

A valid move means choosing two consecutive plus signs:

"++"

and flipping them into:

"--"

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

Function shape:

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

Examples

For:

currentState = "++++"

There are three valid pairs:

So the answer is:

["--++", "+--+", "++--"]

For:

currentState = "+-+"

There is no consecutive "++" pair.

So the answer is:

[]

For:

currentState = "++--++"

There are two valid moves:

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

So the answer is:

["----++", "++----"]

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:

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:

"++"

then one valid next state is:

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:

result = []

Scan every possible adjacent pair:

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

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

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:

n = len(currentState)

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

Implementation

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:

result = []

Then we scan adjacent pairs:

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:

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

The new state is built by replacing only that pair:

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

Then we add it to the answer:

result.append(next_state)

Finally:

return result

returns all possible next states.

Testing

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: