Flip Game

All next states after flipping any consecutive "++" to "--" — linear scan.

Easy
Time O(n^2) Space O(n^2)
LeetCode
2 min read
backtracking string

Problem#

Given a string of + and -, return all possible states after one move that flips any consecutive ++ to --.

Examples#

  • "++++"["--++","+--+","++--"]

Constraints#

  • 1 <= n <= 500.

Approach#

Walk pairs; on every ++, emit a copy with that pair flipped.

Solution#

Flip Game
class Solution {
public:
vector<string> generatePossibleNextMoves(string currentState) {
vector<string> out;
for (int i = 0; i + 1 < (int)currentState.size(); ++i) {
if (currentState[i] == '+' && currentState[i + 1] == '+') {
string s = currentState;
s[i] = s[i + 1] = '-';
out.push_back(s);
}
}
return out;
}
};

Editorial#

Each ++ pair gives a distinct outcome. Copying and editing is the cleanest way; in-place toggle requires a save/restore that costs the same.

Complexity#

  • Time: O(n * n) (copy per emit).
  • Space: O(n * n) for output.

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.