LeetCode 294 - Flip Game II

This problem describes a two-player impartial game played on a string consisting only of '+' and '-' characters. A valid move consists of selecting any pair of consecutive "++" characters and flipping them into "--". The players alternate turns.

leetcodemediummathdynamic-programmingbacktrackingmemoizationgame-theory

LeetCode Problem 294

Difficulty: 🟡 Medium
Topics: Math, Dynamic Programming, Backtracking, Memoization, Game Theory

Solution

Problem Understanding

This problem describes a two-player impartial game played on a string consisting only of '+' and '-' characters. A valid move consists of selecting any pair of consecutive "++" characters and flipping them into "--".

The players alternate turns. If a player cannot make a valid move on their turn, they lose the game. The task is to determine whether the starting player can force a win assuming both players play optimally.

The input is a single string currentState. Each character represents the current board state. The output is a boolean:

  • Return true if the first player has a guaranteed winning strategy.
  • Return false if the second player can always respond optimally and eventually win.

The key phrase in the problem statement is "guarantee a win". This means we are not looking for whether a winning sequence exists by chance, but whether the current player can force victory regardless of how the opponent responds.

The constraints provide several important insights:

  • The string length can be up to 60.
  • There cannot be more than 20 consecutive '+'.

A naive recursive exploration of all game states can become extremely expensive because each move creates multiple branching possibilities. However, the restriction on consecutive '+' sequences significantly limits the actual game tree size in practice.

Several edge cases are important to identify immediately:

  • A string with no "++" substrings means no legal moves exist, so the current player immediately loses.
  • Very short strings such as "+" or "-" cannot contain valid moves.
  • Strings with multiple disconnected "++" regions create branching recursive states.
  • Repeated states can occur through different move orders, making memoization extremely valuable.

This problem is a classic example of recursive game theory with memoization.

Approaches

Brute Force Backtracking

The most direct approach is to recursively simulate every possible move.

For every position in the string, we check whether there is a "++" pair. If there is, we flip it to "--" and recursively determine whether the opponent can win from the resulting state.

The game-theory observation is straightforward:

  • If there exists at least one move that causes the opponent to lose, then the current player wins.
  • If every possible move allows the opponent to win, then the current player loses.

This recursive formulation is correct because the game is finite and deterministic. Eventually every path reaches a terminal state where no moves remain.

However, this brute-force approach recomputes the same states many times. Different sequences of moves can produce identical board configurations, causing exponential duplication of work.

Because of this repeated computation, the naive recursion becomes too slow as the number of possible states grows.

Optimal Approach, DFS with Memoization

The key observation is that the result of a state depends only on the board configuration itself.

If we already know whether a particular string state is winning or losing, we never need to compute it again. This naturally leads to memoization.

We use depth-first search to explore possible moves, and a hash map stores previously computed results:

  • memo[state] = true means the current player can force a win from this state.
  • memo[state] = false means the current player loses with optimal play.

This optimization dramatically reduces repeated computation because each unique state is evaluated only once.

The recursive game-theory rule remains the same:

  • If any move leads to a losing state for the opponent, the current state is winning.
  • Otherwise the current state is losing.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force Exponential, roughly O(2^n) O(n) recursion depth Recomputes identical states many times
Optimal O(S × n) O(S) Uses memoization where S is the number of unique states

Algorithm Walkthrough

  1. Create a memoization map to cache previously computed game states.

The memo prevents recalculating the same board configuration multiple times. Since game states repeat frequently, this optimization is essential. 2. Define a recursive DFS function.

The function takes the current board state as input and returns whether the current player can force a win from that position. 3. Check whether the current state already exists in the memo map.

If the state has been computed before, immediately return the cached result. 4. Iterate through the string and search for "++" pairs.

Every "++" pair represents a legal move that the current player can make. 5. For each valid move, generate the next state.

Replace the selected "++" with "--".

For example:

"++++" → "+--+"
  1. Recursively evaluate the opponent's position.

After making a move, it becomes the opponent's turn. If the recursive call returns false, it means the opponent loses from that state. 7. If any move causes the opponent to lose, mark the current state as winning.

Store the result in the memo map and immediately return true. 8. If all possible moves allow the opponent to win, mark the current state as losing.

Store false in the memo and return it.

Why it works

The algorithm relies on the minimax property of deterministic turn-based games.

A position is winning if at least one legal move transitions into a losing position for the opponent. A position is losing if every legal move transitions into a winning position for the opponent.

Since every recursive call evaluates states according to this rule, and memoization guarantees consistent reuse of computed results, the algorithm correctly determines whether the starting player can force a win.

Python Solution

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 opponent loses, current player wins
                    if not dfs(next_state):
                        memo[state] = True
                        return True

            memo[state] = False
            return False

        return dfs(currentState)

The implementation begins by creating a dictionary called memo. This stores previously computed results for board states.

The nested dfs function performs the recursive game-state evaluation. It first checks whether the current state already exists in the memo table. If so, the cached result is returned immediately.

The loop scans the string looking for "++" pairs. Every valid pair represents a legal move.

When a move is found, the code constructs a new string where the pair is flipped to "--".

The recursive call evaluates whether the opponent can win from the resulting state. If the opponent cannot win, then the current player has found a winning move, so the function stores True and returns immediately.

If the loop finishes without finding a winning move, every possible move leads to an opponent victory. The state is therefore losing, and False is stored in the memo map.

The final result is obtained by calling dfs(currentState).

Go Solution

func canWin(currentState string) bool {
    memo := make(map[string]bool)
    visited := make(map[string]bool)

    var dfs func(string) bool

    dfs = func(state string) bool {
        if visited[state] {
            return memo[state]
        }

        visited[state] = true

        for i := 0; i < len(state)-1; i++ {
            if state[i:i+2] == "++" {
                nextState := state[:i] + "--" + state[i+2:]

                // If opponent loses, current player wins
                if !dfs(nextState) {
                    memo[state] = true
                    return true
                }
            }
        }

        memo[state] = false
        return false
    }

    return dfs(currentState)
}

The Go implementation follows the same recursive memoized structure as the Python version.

One important difference is that Go maps return zero values automatically. Since false is a valid cached result, we need a separate visited map to distinguish between:

  • A state that has not been computed yet
  • A state that has been computed and evaluated to false

String slicing in Go is efficient because strings are immutable byte slices internally. Since the input contains only ASCII characters, indexing and slicing are safe here.

Worked Examples

Example 1

Input: "++++"

Initial state:

Index Pair Valid Move
0 "++" Yes
1 "++" Yes
2 "++" Yes

The algorithm explores moves recursively.

Move 1

Flip indices 0 and 1:

"++++" → "--++"

Opponent turn:

Possible move:

"--++" → "----"

Now no moves remain, so current player loses.

This means the opponent wins from "--++".

So the initial move is not winning.

Move 2

Flip indices 1 and 2:

"++++" → "+--+"

Opponent turn:

There are no "++" pairs.

The opponent immediately loses.

Therefore:

"+--+" is losing for opponent

So "++++" is winning for current player.

Final result:

true

Example 2

Input: "+"

The string length is less than 2, so no "++" pair exists.

The loop never finds a legal move.

Therefore the current player immediately loses.

Final result:

false

Complexity Analysis

Measure Complexity Explanation
Time O(S × n) Each unique state is processed once, and each processing scans the string
Space O(S) Memoization stores all unique states

Here, S represents the number of unique reachable game states.

Without memoization, the recursion repeatedly explores identical states, causing exponential blowup. With memoization, each state is evaluated exactly once, greatly reducing redundant work.

The recursion depth is at most proportional to the number of possible flips, which is bounded by the string length.

Test Cases

solution = Solution()

assert solution.canWin("++++") == True   # Example case with winning move
assert solution.canWin("+") == False     # Single character, no moves
assert solution.canWin("--") == False    # No plus characters
assert solution.canWin("+-") == False    # Mixed characters without valid move
assert solution.canWin("++") == True     # One immediate winning move
assert solution.canWin("+++") == True    # Flip first or last pair
assert solution.canWin("+++++") == False # Optimal play leads to loss
assert solution.canWin("++++++") == True # Multiple branching possibilities
assert solution.canWin("") == False      # Empty string edge case
assert solution.canWin("+--+") == False  # No consecutive pluses
assert solution.canWin("++--++") == False # Multiple isolated regions
assert solution.canWin("++++++++") == True # Larger recursive search

Test Summary

Test Why
"++++" Standard example with winning strategy
"+" Smallest valid input
"--" No legal moves
"+-" Mixed symbols without valid pair
"++" Single possible move
"+++" Overlapping move choices
"+++++" Demonstrates losing configuration
"++++++" Larger branching search
"" Defensive edge-case handling
"+--+" Separated plus symbols
"++--++" Independent regions
"++++++++" Stress test for recursion and memoization

Edge Cases

One important edge case is when the string contains no "++" substring at all. Examples include "+", "--", and "+-+-". A naive implementation might incorrectly assume at least one move exists. In the provided solution, the loop simply never enters the recursive branch, and the state is correctly classified as losing.

Another subtle edge case involves overlapping move positions, such as "+++". There are two valid moves: flipping the first two characters or flipping the last two characters. A buggy implementation might accidentally skip overlapping pairs by advancing indices incorrectly. The solution checks every adjacent pair independently, ensuring all legal moves are explored.

A third important case is repeated states reachable through different paths. Without memoization, the recursion tree can explode exponentially. For example, longer strings like "++++++++" generate many overlapping subproblems. The memo map guarantees each state is computed only once, preventing redundant recursion and ensuring acceptable performance.

A final edge case involves disconnected regions, such as "++--++". The game effectively splits into independent sections, but the recursive search still works naturally because every generated state fully represents the board configuration. No special-case logic is required.