Flip Game II

medium backtracking dp memoization game theory

Problem

Players take turns flipping any consecutive "++" to "--" in the string. The first player who can't move loses. Decide whether the player to move can force a win.

Inputs = "++++"

Outputtrue

Flip middle to get "+--+"; opponent has no move.

def can_win(s):
    memo = {}
    def go(state):
        if state in memo: return memo[state]
        for i in range(len(state) - 1):
            if state[i] == "+" and state[i+1] == "+":
                nxt = state[:i] + "--" + state[i+2:]
                if not go(nxt):
                    memo[state] = True
                    return True
        memo[state] = False
        return False
    return go(s)

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

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

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

Explanation

This is a two-player game, so we reason about it with the classic game-theory rule: the player to move wins if there exists any move that leaves the opponent in a losing position. We turn that sentence directly into recursion.

The function go(state) tries every spot where two + sit side by side. Flipping that pair to -- gives a new state the opponent must now face. We recurse with go(nxt): if the opponent cannot win from nxt (the call returns false), then this move wins for us, so we return true.

If no flip leads to a losing position for the opponent, the current player has no winning move and go returns false. A state with no ++ at all naturally falls through to false — the player who can't move loses.

The same board positions come up over and over, so a memo dictionary caches each state's result. That memoization is what keeps the exponential search manageable.

Example: s = "++++". Flipping the middle gives "+--+", which has no ++ left, so the opponent can't move and loses. Since that winning move exists, canWin("++++") returns true.

Time: O(n!!) Space: O(states)