Problem Description

In the Flip Game II problem, you are given a string s consisting only of the characters '+' and '-'. Two players take turns flipping any two consecutive '+' characters into '--'. The player who cannot make a move loses the game. Your task is to determine if the starting player (the one to move first) can guarantee a win, assuming both players play optimally.

• You can only flip two consecutive '+' characters at a time.
• Once flipped, the '--' cannot be flipped back.
• Players must alternate turns; the first player starts.
• The game ends when no more valid moves can be made.
• Return true if the starting player can guarantee a win; otherwise, return false.

Thought Process

At first glance, it seems we could try every possible move recursively for each player. For each move, we flip two consecutive '+' to '--' and let the other player play. If at any point the current player can force the opponent into a losing position, they can win.

However, this brute-force approach leads to exponential time complexity because the number of possible game states grows rapidly as the string gets longer. To optimize, we need to avoid recalculating the result for the same game state multiple times. This is a classic case for memoization.

The key insight is to represent each unique state of the string and remember if it's a winning or losing position. If the current player can make any move that leaves the opponent in a losing position, then the current position is a winning one.

Solution Approach

Let's break down the optimized solution step by step:

1. Recursion with Memoization:
   • Define a recursive function that, given the current string, returns whether the current player can force a win.
   • Use a hash map (dictionary) to store the result for each string state to avoid recomputation.
2. Try All Possible Moves:
   • For each pair of consecutive '+' in the string, flip them to '--' and recursively check if the opponent loses in the resulting state.
3. Winning Condition:
   • If any move leads to a state where the opponent cannot win (i.e., the recursive call returns false), then the current player can guarantee a win.
4. Base Case:
   • If no valid moves are possible, return false (current player loses).
5. Efficiency:
   • By memoizing, we ensure each unique state is computed only once, making the solution efficient even for longer strings.

Example Walkthrough

Let's consider the input s = "++++".

1. The first player has two possible moves:
   • Flip the first two '+': Resulting string is "--++".
   • Flip the middle two '+': Resulting string is "+--+".
   • Flip the last two '+': Resulting string is "++--".
2. For each resulting string, the second player tries all valid moves:
   • For "--++", the only valid move is flipping the last two '+' to get "----" (no more moves left).
   • For "+--+", the only valid move is flipping the first and last two '+' (but in this case, no two consecutive '+' exist, so no move is possible).
   • For "++--", the only valid move is flipping the first two '+' to get "----".
3. If the first player can force the second player into a position where no moves are left (i.e., the second player loses), the first player wins. In this example, the first player can always win by making the right move.

Code Implementation

class Solution:
    def canWin(self, s: str) -> bool:
        memo = {}
        def can_player_win(state):
            if state in memo:
                return memo[state]
            for i in range(len(state) - 1):
                if state[i] == state[i+1] == '+':
                    next_state = state[:i] + '--' + state[i+2:]
                    if not can_player_win(next_state):
                        memo[state] = True
                        return True
            memo[state] = False
            return False
        return can_player_win(s)
      

class Solution {
public:
    unordered_map<string, bool> memo;
    bool canWin(string s) {
        if (memo.count(s)) return memo[s];
        for (int i = 0; i < s.size() - 1; ++i) {
            if (s[i] == '+' && s[i+1] == '+') {
                s[i] = s[i+1] = '-';
                if (!canWin(s)) {
                    s[i] = s[i+1] = '+';
                    return memo[s] = true;
                }
                s[i] = s[i+1] = '+';
            }
        }
        return memo[s] = false;
    }
};
      

import java.util.HashMap;
public class Solution {
    private HashMap<String, Boolean> memo = new HashMap<>();
    public boolean canWin(String s) {
        if (memo.containsKey(s)) return memo.get(s);
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+') {
                String next = s.substring(0, i) + "--" + s.substring(i + 2);
                if (!canWin(next)) {
                    memo.put(s, true);
                    return true;
                }
            }
        }
        memo.put(s, false);
        return false;
    }
}
      

var canWin = function(s) {
    const memo = new Map();
    function canPlayerWin(state) {
        if (memo.has(state)) return memo.get(state);
        for (let i = 0; i < state.length - 1; i++) {
            if (state[i] === '+' && state[i+1] === '+') {
                let next = state.slice(0, i) + '--' + state.slice(i + 2);
                if (!canPlayerWin(next)) {
                    memo.set(state, true);
                    return true;
                }
            }
        }
        memo.set(state, false);
        return false;
    }
    return canPlayerWin(s);
};
      

Time and Space Complexity

• Brute-force Approach:
  • Time Complexity: Exponential, O(2^n), where n is the length of the string. This is because each move can split the string into new states, and there are many possible move sequences.
  • Space Complexity: O(n) for the recursion stack depth.
• Optimized (Memoization) Approach:
  • Time Complexity: O(2^n), but much faster in practice. Each unique string state is computed only once, and the number of unique states is bounded by 2^n.
  • Space Complexity: O(2^n) for the memoization table, plus O(n) for the recursion stack.

The optimization comes from memoization, which avoids redundant work and makes the solution feasible for strings of moderate length (e.g., up to 20).

Summary

The Flip Game II problem is a classic example of recursive game theory with memoization. By exploring all possible moves and caching results for each game state, we can efficiently determine if the starting player can force a win. The main insight is to recognize and reuse previously computed outcomes for the same board state, which dramatically reduces computation time compared to brute-force recursion. This approach elegantly balances recursion and dynamic programming for optimal performance.