We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Flip Game II

Number: 294

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given a string currentState that contains only '+' and '-', two players take turns flipping two consecutive "++" into "--". The game ends when a player can no longer make a move, and the other player wins. Determine if the starting player can guarantee a win assuming both players play optimally.

Key Insights

  • Transform the problem into a recursion where each valid move generates a new game state.
  • Use backtracking to explore all possible moves.
  • Apply memoization to cache results for previously computed states to avoid repeated work.
  • Leverage game theory: the current player wins if there exists at least one move that forces the opponent into a losing position.

Space and Time Complexity

Time Complexity: O(n * 2^n) in the worst-case scenario; memoization helps prune redundant computations. Space Complexity: O(2^n) for storing all computed game states in the memoization cache plus O(n) recursion depth.

Solution

We solve the problem using recursion with memoization. We recursively try every possible move: for each index in currentState where two consecutive '+' characters appear, we flip them to '--' and call the function recursively to simulate the opponent’s turn. If any move results in a state where the opponent cannot force a win, then the current state is winning for the current player. A cache (memoization) is used to store results for states that have already been computed to save time and avoid redundant recursion.

Code Solutions

# Python implementation with line-by-line comments.
def canWin(currentState: str) -> bool:
    # Dictionary to store the outcome for each state (memoization).
    memo = {}

    def can_win(state: str) -> bool:
        # If the state is already computed, return the cached result.
        if state in memo:
            return memo[state]
        
        # Try every possible move where two consecutive '+' can be flipped.
        for i in range(len(state) - 1):
            if state[i] == '+' and state[i+1] == '+':
                # Generate the next state by flipping the two '+' into '--'.
                next_state = state[:i] + "--" + state[i+2:]
                # If the opponent cannot win from this state, then current state is winning.
                if not can_win(next_state):
                    memo[state] = True
                    return True
        # If no winning move is found, mark the state as losing.
        memo[state] = False
        return False

    return can_win(currentState)

# Example usage:
print(canWin("++++"))
← Back to All Questions