Problem

You are playing a Flip Game with your friend.

You are given a string currentState that contains only '+' and '-'. You and your friend take turns to flip two consecutive "++" into "--". The game ends when a person can no longer make a move, and therefore the other person will be the winner.

Return all possible states of the string currentState after one valid move. You may return the answer in any order. If there is no valid move, return an empty list [].

Examples

Example 1:

Input: currentState = "++++"
Output: ["--++","+--+","++--"]

Example 2:

Input: currentState = "+"
Output: []

Solution

Method 1 - Run the simulation

To solve this problem, we need to identify all possible valid moves where two consecutive ++ characters can be flipped into -- in the given string currentState. Our task is to generate and return all possible states after one valid move.

Approach

  1. Iterate Through the String:
    • Traverse the string and look for occurrences of ++.
  2. Generate New States:
    • For each occurrence of ++, flip it to -- and record the new state.
  3. Return Results:
    • Return a list of all valid new states.

Code

Java
class Solution {
    public List<String> generatePossibleNextMoves(String currentState) {
        List<String> ans = new ArrayList<>();
        int n = currentState.length();

        for (int i = 0; i < n - 1; i++) {
            if (currentState.substring(i, i + 2).equals("++")) {
                String newState = currentState.substring(0, i) + "--" + currentState.substring(i + 2);
                ans.add(newState);
            }
        }

        return ans;
    }
}
Python
class Solution:
    def generatePossibleNextMoves(self, currentState: str) -> List[str]:
        ans: List[str] = []
        n: int = len(currentState)
        
        for i in range(n - 1):
            if currentState[i:i+2] == "++":
                new_state = currentState[:i] + "--" + currentState[i+2:]
                ans.append(new_state)
        
        return ans

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string currentState. This is because we make a single pass through the string, and generating each new state takes O(n) time (copying the string into a new list).
  • 🧺 Space complexity: O(n * m), where m is the number of valid moves. This space is used to store the resultant states in the list.