LeetCode 293: Flip Game Solution in Python – A Step-by-Step Guide

What Is LeetCode 293: Flip Game?

In LeetCode 293: Flip Game, you’re given a string currentState made of only "+" and "-" characters (e.g., "++++"). In one move, you can pick any two consecutive "++" and change them to "--". Your job is to return a list of all possible strings you could make after one flip. For example, with "++++", you can flip the first pair to get "--++", the middle pair to get "+--+", or the last pair to get "++--". This problem tests your ability to find and modify patterns in a string, sharing a vibe with string manipulation tasks like LeetCode 344: Reverse String.

Problem Statement

• Input: A string currentState containing only "+" and "-".
• Output: A list of strings, each representing a possible state after flipping one "++" to "--".
• Rules: Flip two consecutive "+" to "--"; return all possibilities; if no "++", return empty list.

Constraints

• currentState length: 0 to 500.
• Contains only "+" and "-".

Examples

• Input: currentState = "++++"
• Output: ["--++", "+--+", "++--"]
• Input: currentState = "+-+"
• Output: [] (no "++" to flip)
• Input: currentState = "++"
• Output: ["--"]

Understanding the Problem: Flipping the Signs

To solve LeetCode 293: Flip Game in Python, we need to take currentState, find every spot where two "+" signs sit side by side ("++"), and create a new string for each spot by flipping those two to "--". For "++++", there are three "++" pairs (positions 0-1, 1-2, 2-3), so we make three new strings. If there’s no "++", like in "+-+", we return an empty list. It’s a straightforward search-and-replace task, and we’ll tackle it with:

• Best Solution (Linear Scan with String Replacement): O(n) time, O(n) space—simple and quick.
• Alternative Solution (Two-Pointer Approach): O(n) time, O(n) space—more manual but clear.

Let’s dive into the linear scan solution with a friendly breakdown that’s easy to follow.

Best Solution: Linear Scan with String Replacement

Why This Is the Best Solution

The linear scan with string replacement is the top choice for LeetCode 293 because it’s fast—O(n) time, where n is the string length—and uses O(n) space to store the results, which is perfect for this task. It slides through the string once, spots every "++", and builds new strings with a flip, all in a clean, simple way. It’s like running your finger along a line of signs, flipping pairs as you go—easy and efficient!

How It Works

Let’s picture this like flipping switches on a board:

• Step 1: Look for Pairs:
• Start at the beginning of the string and check each character with the one next to it—like "++" at positions 0 and 1.
• Step 2: Flip and Save:
• When you find "++", make a new string:
• Take everything before the pair.
• Add "--" instead of "++".
• Add everything after.
• Save that new string in a list.
• Step 3: Move Along:
• Slide to the next spot and repeat until you’ve checked the whole string.
• Step 4: Why It Works:
• Checking each pair (i with i+1) catches every "++" exactly once.
• String slicing lets us swap "++" to "--" without messing up the original.
• We get all possible flips in one smooth pass.

It’s like spotting every pair of lights and flipping them off—one easy sweep!

Step-by-Step Example

Example: currentState = "++++"

• Initial: "++++", result list = [].
• Position 0:
• Check "++" at 0-1.
• New string: "" + "--" + "++" = "--++".
• Result: ["--++"].
• Position 1:
• Check "++" at 1-2.
• New string: "+" + "--" + "+" = "+--+".
• Result: ["--++", "+--+"].
• Position 2:
• Check "++" at 2-3.
• New string: "++" + "--" + "" = "++--".
• Result: ["--++", "+--+", "++--"].
• Position 3: Only one character left, stop.
• Result: ["--++", "+--+", "++--"].

Example: currentState = "+-+"

• Check: No "++" anywhere—0-1 is "+-", 1-2 is "-+".
• Result: [].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def generatePossibleNextMoves(self, currentState: str) -> List[str]:
        # Step 1: Set up a list for results
        result = []

        # Step 2: Check each pair of characters
        for i in range(len(currentState) - 1):  # Stop before last char
            # Step 3: Look for "++"
            if currentState[i:i+2] == "++":  # Check two chars at i and i+1
                # Step 4: Make a new string with "--"
                new_state = currentState[:i] + "--" + currentState[i+2:]
                result.append(new_state)  # Add it to the list

        # Step 5: Return all possible flips
        return result

• Line 4: Make an empty list to hold all the new strings.
• Line 7: Loop from 0 to length-2 (since we check i and i+1).
• Line 9: Use slicing i:i+2 to grab two characters—if they’re "++", we’ve got a match!
• Line 11: Build the new string:
• [:i] takes everything before the pair.
• "--" replaces the "++".
• [i+2:] takes everything after.
• Line 12: Add the new string to our result list.
• Line 14: Return the full list of possibilities.

• Time Complexity: O(n)—one pass through the string, string ops are O(n).
• Space Complexity: O(n)—stores result strings, proportional to input size.

This is like a quick flip trick—spot, swap, save!

Alternative Solution: Two-Pointer Approach

Why an Alternative Approach?

The two-pointer approach also runs in O(n) time and O(n) space but uses two indices to manually track the pair—more hands-on than slicing. It’s a bit more explicit, like pointing at each pair with your fingers, and great for seeing the mechanics step-by-step.

How It Works

Let’s think of this like walking two pointers along:

• Step 1: Set two pointers, left and right, starting with right = left + 1.
• Step 2: Check the pair at left and right:
• If "++", flip to "--" and save the new string.
• Step 3: Move left up one, set right = left + 1, repeat until the end.
• Step 4: Collect all new strings.

It’s like sliding a window of two spots across the string!

Step-by-Step Example

Example: currentState = "++++"

• Initial: left=0, right=1, result = [].
• left=0, right=1: "++" → "--++", result = ["--++"].
• left=1, right=2: "++" → "+--+", result = ["--++", "+--+"].
• left=2, right=3: "++" → "++--", result = ["--++", "+--+", "++--"].
• left=3: right out of bounds, stop.
• Result: ["--++", "+--+", "++--"].

Code for Two-Pointer Approach

Copy codeclass Solution:
    def generatePossibleNextMoves(self, currentState: str) -> List[str]:
        result = []
        left = 0

        while left < len(currentState) - 1:
            right = left + 1
            if currentState[left] == "+" and currentState[right] == "+":
                new_state = currentState[:left] + "--" + currentState[right+1:]
                result.append(new_state)
            left += 1

        return result

• Time Complexity: O(n)—one pass, string ops O(n).
• Space Complexity: O(n)—result list.

It’s a manual flip-by-flip check!

Comparing the Two Solutions

• Linear Scan (Best):
• Pros: O(n) time, O(n) space, clean and concise.
• Cons: Relies on slicing.
• Two-Pointer (Alternative):
• Pros: O(n) time, O(n) space, explicit pair tracking.
• Cons: Slightly more code.

Linear scan wins for simplicity.

Additional Examples and Edge Cases

• "+": [] (no pair).
• "++": ["--"].
• "": [] (empty).

Both handle these perfectly.

Complexity Breakdown

• Linear Scan: Time O(n), Space O(n).
• Two-Pointer: Time O(n), Space O(n).

Linear scan’s the champ.

Key Takeaways

• Linear Scan: Slide and flip—easy!
• Two-Pointer: Point and flip—clear!
• Strings: Pattern spotting is fun.
• Python Tip: Slicing rocks—see [Python Basics](/python/basics).

Final Thoughts: Flip to Win

LeetCode 293: Flip Game in Python is a playful string challenge. The linear scan solution flips fast, while two-pointers show the steps. Want more? Try LeetCode 344: Reverse String or LeetCode 294: Flip Game II. Ready to flip? Head to Solve LeetCode 293 on LeetCode and make those moves today!