Flip Game II solution and explanation
Google
The problem
You are playing a Flip Game with your friend.
You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.
Return true if the starting player can guarantee a win, and false otherwise.
Example 1:
Input: currentState = "++++" Output: true Explanation: The starting player can guarantee a win by flipping the middle "++" to become "+--+".
Example 2:
Input: currentState = "+" Output: false
Constraints:
1 <= currentState.length <= 60currentState[i]is either'+'or'-'.- There cannot be more than 20 consecutive
'+'.
Approach overview
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.
Solution
class Solution:
def canWin(self, currentState: str) -> bool:
@cache
def dfs(mask):
for i in range(n - 1):
if (mask & (1 << i)) == 0 or (mask & (1 << (i + 1)) == 0):
continue
if dfs(mask ^ (1 << i) ^ (1 << (i + 1))):
continue
return True
return False
mask, n = 0, len(currentState)
for i, c in enumerate(currentState):
if c == '+':
mask |= 1 << i
return dfs(mask)class Solution {
private int n;
private Map<Long, Boolean> memo = new HashMap<>();
public boolean canWin(String currentState) {
long mask = 0;
n = currentState.length();
for (int i = 0; i < n; ++i) {
if (currentState.charAt(i) == '+') {
mask |= 1 << i;
}
}
return dfs(mask);
}
private boolean dfs(long mask) {
if (memo.containsKey(mask)) {
return memo.get(mask);
}
for (int i = 0; i < n - 1; ++i) {
if ((mask & (1 << i)) == 0 || (mask & (1 << (i + 1))) == 0) {
continue;
}
if (dfs(mask ^ (1 << i) ^ (1 << (i + 1)))) {
continue;
}
memo.put(mask, true);
return true;
}
memo.put(mask, false);
return false;
}
}using ll = long long;
class Solution {
public:
int n;
unordered_map<ll, bool> memo;
bool canWin(string currentState) {
n = currentState.size();
ll mask = 0;
for (int i = 0; i < n; ++i)
if (currentState[i] == '+') mask |= 1ll << i;
return dfs(mask);
}
bool dfs(ll mask) {
if (memo.count(mask)) return memo[mask];
for (int i = 0; i < n - 1; ++i) {
if ((mask & (1ll << i)) == 0 || (mask & (1ll << (i + 1))) == 0) continue;
if (dfs(mask ^ (1ll << i) ^ (1ll << (i + 1)))) continue;
memo[mask] = true;
return true;
}
memo[mask] = false;
return false;
}
};func canWin(currentState string) bool {
n := len(currentState)
memo := map[int]bool{}
mask := 0
for i, c := range currentState {
if c == '+' {
mask |= 1 << i
}
}
var dfs func(int) bool
dfs = func(mask int) bool {
if v, ok := memo[mask]; ok {
return v
}
for i := 0; i < n-1; i++ {
if (mask&(1<<i)) == 0 || (mask&(1<<(i+1))) == 0 {
continue
}
if dfs(mask ^ (1 << i) ^ (1 << (i + 1))) {
continue
}
memo[mask] = true
return true
}
memo[mask] = false
return false
}
return dfs(mask)
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Pure Backtracking (Game Tree Exploration) | O(n * 2^n) | O(2^n) | Useful for understanding the game logic and recursive state exploration |
| Backtracking with Memoization | O(n * 2^n) | O(2^n) | Best practical solution; avoids recomputing previously evaluated board states |
Frequently asked questions
Is Flip Game II easy or hard?
Flip Game II is generally considered a medium difficulty problem. The recursion logic is straightforward, but recognizing the need for memoization and reasoning about winning versus losing states requires familiarity with backtracking and game theory patterns.
Flip Game II Python/Java solution
In Python or Java, implement a recursive DFS that scans the string for "++" pairs. Replace them with "--", call the function for the opponent’s turn, then restore the string. Use a hash map keyed by the string state to memoize results and avoid recomputation.
How to solve Flip Game II in O(n)?
An exact O(n) general solution is not typically used for this problem because the state space depends on all possible game configurations. The common interview solution uses backtracking with memoization and runs in roughly O(n * 2^n). More advanced theoretical solutions use combinatorial game theory, but they are rarely required in interviews.
What is the best approach for Flip Game II?
Backtracking with memoization is the most effective approach. The algorithm tries every possible "++" flip and recursively checks if the opponent loses from the resulting state. A hash map caches previously evaluated board configurations so each state is computed once. This reduces repeated work across the game tree.
Is Flip Game II asked at Google/Amazon/Meta?
Flip Game II represents a classic game‑theory recursion problem and has appeared in interview preparation sets associated with companies like Google, Amazon, and Meta. Interviewers use it to evaluate reasoning about winning states, recursion, and memoization.
What data structure is used in Flip Game II?
A hash map (or dictionary) is used for memoization to store previously evaluated board states. Recursion explores possible moves, while the map quickly returns results for repeated configurations. Strings or character arrays represent the board state.
What is the time complexity of Flip Game II?
The typical memoized DFS solution runs in O(n * 2^n) time in the worst case. Each unique board configuration may be explored once, and generating next states requires scanning the string for "++" pairs. Space complexity is O(2^n) for recursion and memo storage.