Flip Game solution and explanation
Google
8 more videos on this problem
293. Flip Game - Week 1/5 Leetcode February ChallengeProgramming Live with Larry · 3:50 · 416 views
LeetCode 293: Flip Game - Uncover Optimal Strategies and Detailed Solutions to Enhance Coding Skillsleetcode blind 75 · 2:08 · 324 views
293. Flip Game (LeetCode, Java)hakunamatasq · 4:35 · 255 views
Cracking the coding interview with LeetCode Premium for FREE: 293 Flip GameSuper Lazy Coder · 10:12 · 136 views
LeetCode 293 | Flip Game | String | Debug | JavaSleepy Cracker · 3:40 · 105 views
🧩 LeetCode or Die: 293 | Flip GamecensoredHacker · 42:34 · 52 views
Leetcode | 293. Flip Game | Approach: Linear Iteration | Easy | JavascriptSoftware Interviews Prep · 7:33 · 42 views
Cracking The LeetCode Flip GametaylorCodes · 5:48 · 13 views
LeetCode 293: Flip GameAlitaCode · 26:32 · 9 views
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 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 <= 500currentState[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).
class Solution:
def generatePossibleNextMoves(self, currentState: str) -> List[str]:
s = list(currentState)
ans = []
for i, (a, b) in enumerate(pairwise(s)):
if a == b == "+":
s[i] = s[i + 1] = "-"
ans.append("".join(s))
s[i] = s[i + 1] = "+"
return ansclass Solution {
public List<String> generatePossibleNextMoves(String currentState) {
List<String> ans = new ArrayList<>();
char[] s = currentState.toCharArray();
for (int i = 0; i < s.length - 1; ++i) {
if (s[i] == '+' && s[i + 1] == '+') {
s[i] = '-';
s[i + 1] = '-';
ans.add(new String(s));
s[i] = '+';
s[i + 1] = '+';
}
}
return ans;
}
}class Solution {
public:
vector<string> generatePossibleNextMoves(string s) {
vector<string> ans;
for (int i = 0; i < s.size() - 1; ++i) {
if (s[i] == '+' && s[i + 1] == '+') {
s[i] = s[i + 1] = '-';
ans.emplace_back(s);
s[i] = s[i + 1] = '+';
}
}
return ans;
}
};function generatePossibleNextMoves(currentState: string): string[] {
const s = currentState.split('');
const ans: string[] = [];
for (let i = 0; i < s.length - 1; ++i) {
if (s[i] === '+' && s[i + 1] === '+') {
s[i] = s[i + 1] = '-';
ans.push(s.join(''));
s[i] = s[i + 1] = '+';
}
}
return ans;
}func generatePossibleNextMoves(currentState string) (ans []string) {
s := []byte(currentState)
for i := 0; i < len(s)-1; i++ {
if s[i] == '+' && s[i+1] == '+' {
s[i], s[i+1] = '-', '-'
ans = append(ans, string(s))
s[i], s[i+1] = '+', '+'
}
}
return
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n^2) | O(n) | Simple implementation when learning basic string scanning and result generation |
| Traversal + Simulation | O(n^2) | O(n) | Preferred interview solution with cleaner logic and minimal repeated substring operations |
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.