Flip Game - Practice Coding Problems

Flip Game - Problem

String Easy

You are playing a Flip Game with your friend. You are given a string currentState that contains only '+' and '-' characters.

You and your friend take turns to flip two consecutive "+" characters into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list.

Input & Output

Example 1 — Single ++ Pair

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

› Output: ["+----"]

💡 Note: Only one ++ pair exists at positions 3-4, flipping it gives "+----"

Example 2 — Multiple ++ Pairs

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

› Output: ["----++", "++----"]

💡 Note: Two ++ pairs: positions 0-1 and 4-5. Flipping first gives "----++", flipping second gives "++----"

Example 3 — No Valid Moves

$ Input: currentState = "+-+-"

› Output: []

💡 Note: No consecutive ++ pairs exist, so no valid moves possible

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

String with + and - characters

Process

Find all ++ patterns and flip each to --

Output

Array of all possible states after one move

Key Takeaway

🎯 Key Insight: Scan for consecutive '+' pairs and generate new states by flipping each to '--'

Asked in

G Google 15 f Facebook 12

The key insight is to scan the string for consecutive ++ patterns and generate a new state for each one found by flipping to --. Best approach is linear scan with Time: O(n²), Space: O(n×k) where k is number of moves.

Common Approaches

Approach	Time	Space	Notes
✓ Linear Scan	O(n²)	O(n×k)	Scan through string and generate new state for each '++' pair found

Linear Scan — Algorithm Steps

Scan string from left to right
When '++' is found, create new string with those positions as '--'
Add the new state to result list

Visualization

Tap to expand

Step-by-Step Walkthrough

Scan String

Look for consecutive + characters

Create New State

Flip ++ to -- for each occurrence

Collect Results

Add all possible states to result

Code -

solution.c — C

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

char** solution(char* currentState, int* returnSize) {
    int n = strlen(currentState);
    char** result = malloc(n * sizeof(char*));
    *returnSize = 0;
    
    for (int i = 0; i < n - 1; i++) {
        if (currentState[i] == '+' && currentState[i + 1] == '+') {
            // Create new state by flipping ++ to --
            char* newState = malloc((n + 1) * sizeof(char));
            strncpy(newState, currentState, i);
            newState[i] = '-';
            newState[i + 1] = '-';
            strcpy(newState + i + 2, currentState + i + 2);
            result[*returnSize] = newState;
            (*returnSize)++;
        }
    }
    
    return result;
}

int main() {
    char currentState[1000];
    fgets(currentState, sizeof(currentState), stdin);
    currentState[strcspn(currentState, "\n")] = 0;
    
    int returnSize;
    char** result = solution(currentState, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("\"%s\"", result[i]);
        if (i < returnSize - 1) printf(",");
        free(result[i]);
    }
    printf("]\n");
    free(result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n²)

O(n) to scan string, O(n) to create each new string, up to O(n) possible flips

⚠ Quadratic Growth

Space Complexity

O(n×k)

Storing k result strings, each of length n

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~15 min Avg. Time

892 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

Linear Scan — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler