Skip to main content
Talentd

Flip Game - Solution & Explanation

EasyPremiumFree on FleetCodeString6 min readAsked at: Google
Practice this problem

Problem Statement

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 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 [].

 

Example 1:

Input: currentState = "++++"
Output: ["--++","+--+","++--"]

Example 2:

Input: currentState = "+"
Output: []

 

Constraints:

  • 1 <= currentState.length <= 500
  • currentState[i] is either '+' or '-'.

Approach Overview

Problem Overview: You are given a string containing only '+' and '-'. A valid move flips any consecutive "++" into "--". Return all possible strings you can generate after making exactly one valid move.

Approach 1: Brute Force Pair Check (O(n^2) time, O(n) space)

Scan the string and examine every pair of adjacent characters. Whenever you find "++", construct a new string where that pair becomes "--". Because strings are immutable in most languages, creating the new string requires concatenating the prefix, the flipped pair, and the suffix. Each creation costs O(n), and you may check up to n positions, giving O(n^2) time overall with O(n) extra space per generated state. This approach is straightforward and commonly used when practicing basic string manipulation problems.

Approach 2: Traversal + Simulation (O(n^2) time, O(n) space)

Traverse the string once and simulate the flip when a valid pair appears. Instead of rebuilding the string using multiple substrings each time, convert the string to a mutable character array (or temporarily modify characters). When you encounter "++", flip the two characters to '-', record the resulting string, and then revert the change before continuing the traversal. This technique reduces repeated substring operations and keeps the logic clean. The scan itself is O(n), but each generated state still requires building a string of length n, so the total time remains O(n^2). The idea is a typical simulation pattern combined with simple traversal over a string.

Recommended for interviews: Interviewers expect the traversal + simulation solution. It demonstrates that you can iterate through the string, detect valid patterns, and generate new states without unnecessary work. Starting with the brute force explanation shows clear reasoning, while implementing the simulation version proves you can write efficient string manipulation code under interview constraints.

Solution

We traverse the string. If the current character and the next character are both +, we change these two characters to -, add the result to the result array, and then change these two characters back to +.

After the traversal ends, we return the result array.

The time complexity is O(n^2), where n is the length of the string. Ignoring the space complexity of the result array, the space complexity is O(n) or O(1).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Pair CheckO(n^2)O(n)Simple implementation when learning basic string scanning and result generation
Traversal + SimulationO(n^2)O(n)Preferred interview solution with cleaner logic and minimal repeated substring operations

Video Solution

293. Flip Game - Week 1/5 Leetcode February Challenge • Programming Live with Larry • 416 views views

Watch 8 more video solutions →

Frequently Asked Questions

Is Flip Game easy or hard?
Flip Game is classified as an Easy problem. It mainly tests the ability to traverse a string, detect patterns, and generate new states through simple simulation.
Flip Game Python/Java solution
In Python or Java, iterate through the string and check if s[i] and s[i+1] form "++". When found, create a new string with that pair replaced by "--" and add it to the result list. Continue scanning until the end of the string.
How to solve Flip Game in O(n)?
Generating all resulting strings prevents a strict O(n) solution because each result itself is length n. The optimal approach scans the string once to find "++" pairs and constructs new strings for each valid flip, resulting in O(n^2) total time.
What is the best approach for Flip Game?
The traversal and simulation approach is the most practical solution. Iterate through the string and whenever you see "++", flip it to "--" and record the resulting string. This scans the string once and generates each valid state, leading to O(n^2) time due to string construction.
Is Flip Game asked at Google/Amazon/Meta?
Flip Game is a common easy-level interview question used to evaluate basic string manipulation and simulation skills. Variants of the problem and its follow-up (Flip Game II) have appeared in interviews at companies like Google and Amazon.
What data structure is used in Flip Game?
The main data structure is a string or character array. The algorithm iterates through the string, checks adjacent characters, and builds new strings representing each valid flip state.
What is the time complexity of Flip Game?
The overall time complexity is O(n^2). You scan the string in O(n), but each valid flip requires constructing a new string of length n. Space complexity is O(n) for storing generated states.

Ready to solve this problem?

Practice Flip Game with our built-in code editor and test cases.

Practice on FleetCode
Previous

Flip Game II