Flip Game - Solution & Explanation

Problem Overview: You’re given a string containing only '+' and '-'. A valid move flips two consecutive '++' into '--'. The task is to return every possible string you can generate after performing exactly one valid move.

Approach 1: Brute Force String Construction (O(n^2) time, O(k * n) space)

Scan the string from left to right and check every pair of adjacent characters. Whenever you see "++", construct a new string where that pair becomes "--". Because strings are immutable in many languages, building the new state usually requires slicing the prefix, adding "--", and appending the remaining suffix.

Each valid flip creates a new string of length n. If there are k valid positions, you generate k strings, and each creation takes O(n). The scan itself is O(n), but the repeated string construction leads to O(n^2) in the worst case. This approach is straightforward and demonstrates clear understanding of the problem.

Approach 2: Char Array Simulation (O(n) time, O(k * n) space)

Convert the string into a mutable character array. Iterate through the array and check whether chars[i] and chars[i+1] form "++". When they do, temporarily flip them to '-', record the resulting string, then revert the characters back to '+'. This avoids repeated substring concatenation.

The key insight is that the string itself never changes permanently. You simulate each move in-place, capture the state, and immediately restore the original characters before moving forward. The scan across the string is linear, so the algorithm runs in O(n) time while generating up to k result strings.

This pattern appears often in string manipulation and simulation problems where you need to explore multiple states derived from small local modifications.

Recommended for interviews: The in-place simulation approach is typically expected. It keeps the logic simple while avoiding unnecessary substring allocations. Starting with the brute force idea shows you understand the problem mechanics, but the optimized version demonstrates stronger control over string handling and iteration patterns.