Is Flip Game easy or hard?

Flip Game is classified as an Easy problem. It mainly tests the ability to traverse a string, detect patterns, and generate new states through simple simulation.

Flip Game Python/Java solution

In Python or Java, iterate through the string and check if s[i] and s[i+1] form "++". When found, create a new string with that pair replaced by "--" and add it to the result list. Continue scanning until the end of the string.

How to solve Flip Game in O(n)?

Generating all resulting strings prevents a strict O(n) solution because each result itself is length n. The optimal approach scans the string once to find "++" pairs and constructs new strings for each valid flip, resulting in O(n^2) total time.

What is the best approach for Flip Game?

The traversal and simulation approach is the most practical solution. Iterate through the string and whenever you see "++", flip it to "--" and record the resulting string. This scans the string once and generates each valid state, leading to O(n^2) time due to string construction.

Is Flip Game asked at Google/Amazon/Meta?

Flip Game is a common easy-level interview question used to evaluate basic string manipulation and simulation skills. Variants of the problem and its follow-up (Flip Game II) have appeared in interviews at companies like Google and Amazon.

What data structure is used in Flip Game?

The main data structure is a string or character array. The algorithm iterates through the string, checks adjacent characters, and builds new strings representing each valid flip state.

What is the time complexity of Flip Game?

The overall time complexity is O(n^2). You scan the string in O(n), but each valid flip requires constructing a new string of length n. Space complexity is O(n) for storing generated states.

Description Solution Video 3:50

293. Flip Game

Easy64.8% acceptance1 companyPremium elsewhere, free here

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 [].

Example 1:

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

Example 2:

Input: currentState = "+"
Output: []

Constraints:

1 <= currentState.length <= 500
currentState[i] is either '+' or '-'.

Asked at 1 company

Google

Topics

String

3:50

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

293. Flip Game

Asked at 1 company

Topics

Similar problems