Flip Game

easy string

Problem

Given a string of '+' and '-', find every state you can reach in one move by flipping any two consecutive "++" into "--".

Inputs = "++++"

Output["--++", "+--+", "++--"]

def generate(s):
    out = []
    for i in range(len(s) - 1):
        if s[i] == '+' and s[i + 1] == '+':
            out.append(s[:i] + '--' + s[i + 2:])
    return out

function generate(s) {
  const out = [];
  for (let i = 0; i < s.length - 1; i++) {
    if (s[i] === '+' && s[i + 1] === '+')
      out.push(s.slice(0, i) + '--' + s.slice(i + 2));
  }
  return out;
}

class Solution {
    public List<String> generatePossibleNextMoves(String s) {
        List<String> out = new ArrayList<>();
        for (int i = 0; i < s.length() - 1; i++)
            if (s.charAt(i) == '+' && s.charAt(i + 1) == '+')
                out.add(s.substring(0, i) + "--" + s.substring(i + 2));
        return out;
    }
}

vector<string> generatePossibleNextMoves(string s) {
    vector<string> out;
    for (int i = 0; i < (int)s.size() - 1; i++)
        if (s[i] == '+' && s[i + 1] == '+')
            out.push_back(s.substr(0, i) + "--" + s.substr(i + 2));
    return out;
}

Explanation

One move in this game means finding two side-by-side plus signs ("++") and flipping them to minuses ("--"). We want every string reachable in a single move, so we just try flipping each "++" pair, one at a time.

We slide a window across the string looking at each adjacent pair s[i] and s[i+1]. Whenever both are '+', we build a new string that is the part before, then "--", then the part after, and add it to out.

Each pair is treated independently — we always start from the original string, so flipping one pair never affects how we test another.

Example: s = "++++". The "++" pairs sit at positions 0, 1, and 2, giving "--++", "+--+", and "++--".

There are about n pairs to check, and building each new string copies up to n characters, which is why both time and output size grow with n².

Time: O(n²) Space: O(n²) for the output