Flip Game - Solution & Explanation

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.