Flip Game
All next states after flipping any consecutive "++" to "--" — linear scan.
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#
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; }};func generatePossibleNextMoves(currentState string) []string { out := []string{} for i := 0; i+1 < len(currentState); i++ { if currentState[i] == '+' && currentState[i+1] == '+' { b := []byte(currentState) b[i] = '-' b[i+1] = '-' out = append(out, string(b)) } } return out}from typing import List
class Solution: def generatePossibleNextMoves(self, currentState: str) -> List[str]: out: List[str] = [] for i in range(len(currentState) - 1): if currentState[i] == '+' and currentState[i + 1] == '+': out.append(currentState[:i] + '--' + currentState[i + 2:]) return outvar generatePossibleNextMoves = function(currentState) { const out = []; for (let i = 0; i + 1 < currentState.length; i++) { if (currentState[i] === '+' && currentState[i + 1] === '+') { out.push(currentState.slice(0, i) + '--' + currentState.slice(i + 2)); } } return out;};class Solution { public List<String> generatePossibleNextMoves(String currentState) { List<String> out = new ArrayList<>(); char[] arr = currentState.toCharArray(); for (int i = 0; i + 1 < arr.length; i++) { if (arr[i] == '+' && arr[i + 1] == '+') { char[] copy = arr.clone(); copy[i] = '-'; copy[i + 1] = '-'; out.add(new String(copy)); } } return out; }}function generatePossibleNextMoves(currentState: string): string[] { const out: string[] = []; for (let i = 0; i + 1 < currentState.length; i++) { if (currentState[i] === '+' && currentState[i + 1] === '+') { out.push(currentState.slice(0, i) + '--' + currentState.slice(i + 2)); } } 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#
Related#