Flip Game II - Solution & Explanation

Problem Overview: You receive a string containing '+' and '-'. A move flips any consecutive "++" into "--". Players alternate turns. If a player cannot make a move, they lose. The task is to determine whether the starting player has a guaranteed winning strategy.

Approach 1: Pure Backtracking (Game Simulation) (Time: O(n * 2^n), Space: O(2^n))

Simulate the game directly. Iterate through the string and look for every "++". For each occurrence, flip it to "--" and recursively check if the opponent can win from the resulting state. If any move leads to a position where the opponent loses, the current player wins. This explores the entire game tree, which grows exponentially because each state can branch into several new states.

The key insight is standard two-player game reasoning: if you can move to a state where the opponent has no winning move, your current state is winning. Without caching, the same board configuration may be recomputed many times, making this approach impractical for longer strings.

Approach 2: Backtracking with Memoization (Optimal) (Time: O(n * 2^n), Space: O(2^n))

Store previously computed states in a hash map so the same configuration is evaluated only once. Each recursive call checks whether the current string already exists in the memo table. If it does, return the stored result immediately. Otherwise iterate through the string, flip each "++", and recursively evaluate the opponent’s position.

If any generated state returns false (opponent loses), mark the current state as true and store it in the memo map. This pruning drastically reduces repeated computation across the game tree. The approach is essentially a depth‑first search over possible states combined with caching, a common pattern in backtracking and memoization problems.

Conceptually, the problem is also related to impartial combinatorial games where positions are classified as winning or losing states. Instead of computing full Grundy numbers from game theory, the memoized DFS simply checks if a losing child state exists.

Recommended for interviews: Backtracking with memoization is the expected solution. Starting with brute force shows you understand the game simulation, but adding memoization demonstrates awareness of overlapping subproblems and converts the search into an efficient dynamic exploration of states, similar to techniques used in dynamic programming.