Flip Game II - Practice Coding Problems

Flip Game II - Problem

Math Dynamic Programming Backtracking Memoization Game Theory Medium

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.

Input & Output

Example 1 — Basic Winning Case

$ Input: currentState = "++++"

› Output: true

💡 Note: Player 1 can flip the first two ++ to get "--++", then no matter what player 2 does, player 1 can win on the next turn.

Example 2 — No Winning Move

$ Input: currentState = "+"

› Output: false

💡 Note: Player 1 cannot make any move since there are no consecutive ++ pairs, so player 1 loses immediately.

Example 3 — Complex Case

$ Input: currentState = "++--++"

› Output: true

💡 Note: Player 1 has two possible moves: flip first ++ or last ++. At least one of these moves leads to a winning strategy.

Constraints

1 ≤ currentState.length ≤ 20
currentState[i] is either '+' or '-'

Visualization

Tap to expand

Understanding the Visualization

Input

String with + and - characters

Game Rule

Flip consecutive ++ to -- alternately

Win Condition

Player who cannot move loses

Key Takeaway

🎯 Key Insight: A game position is winning if there exists at least one move that puts the opponent in a losing position

Asked in

G Google 15 f Facebook 12 M Microsoft 8 a Amazon 6

The key insight is to use game theory: a position is winning if there exists at least one move that leads to a losing position for the opponent. The memoized recursion approach is optimal, avoiding redundant calculations by caching results. Time: O(n × 2^n), Space: O(2^n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force Recursion	O(2^n)	O(n)	Try all possible moves recursively without memoization
Memoized Recursion	O(n × 2^n)	O(2^n)	Cache results of previously computed game states to avoid redundant calculations

Brute Force Recursion — Algorithm Steps

Find all positions with "++"
For each position, flip to "--" and recurse
If any recursive call returns false (opponent loses), return true

Visualization

Tap to expand

Step-by-Step Walkthrough

Find Moves

Identify all "++" positions

Try Each Move

Recursively check each possible flip

Win Condition

Win if any move leads to opponent losing

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

bool canWin(char* state) {
    int len = strlen(state);
    // Try all possible moves
    for (int i = 0; i < len - 1; i++) {
        if (state[i] == '+' && state[i + 1] == '+') {
            // Make the move: flip ++ to --
            char* newState = malloc(len + 1);
            strcpy(newState, state);
            newState[i] = '-';
            newState[i + 1] = '-';
            // If opponent cannot win from this state, current player wins
            if (!canWin(newState)) {
                free(newState);
                return true;
            }
            free(newState);
        }
    }
    // No winning move found
    return false;
}

bool solution(char* currentState) {
    return canWin(currentState);
}

int main() {
    char currentState[1000];
    fgets(currentState, sizeof(currentState), stdin);
    currentState[strcspn(currentState, "\n")] = 0;
    bool result = solution(currentState);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n)

Each position can branch into multiple states, leading to exponential recursive calls

⚠ Quadratic Growth

Space Complexity

O(n)

Recursion depth is at most n (number of ++ pairs), plus string copies

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force Recursion — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler