Valley of depression

Moderate

0/80

0 upvote

Problem statement

After getting around 30+ referrals from a FAANG company Ninja could not able to get a single interview call. This makes Ninja very frustrated. So Ninja tried to increase his reachability by posting random stuff on a job searching platform so that a recruiter might contact him.

Fortunately, one Legendary Grandmaster(LGM) coder on CodeStudio contacted Ninja for a job offer and LGM gave Ninja a problem to solve. As Ninja is in a state of mental depression due to so many rejections. So he called you for help.

Given a string S, consisting of only the '(' or ')' parenthesis. Your task is to make the string balanced by doing the following operation zero or more times:

1. Choose a parenthesis from the string and remove it.

You need to print all possible balanced strings that can be formed from the given string by doing the above operation zero or more times.

The fate of Ninja lies in your hand.

Note:

Print only those distinct strings that can be formed by removing the minimum number of parentheses.

If the string is already balanced, return the original string.

For example:

(()

Expected string is:

[ () ]

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains an integer 'T' which denotes the number of test cases or queries to be run.

The first line of each test case contains a string ‘S’ which contains the parentheses.

Output Format:

For each case, If the returned strings are correct then the output will be 1, else  0.

The output of each test case will be printed on a separate line.

Note:

You can return strings in any order.

You do not need to input or print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 5
1 <= |S| <= 15

Timit Limit: 1 sec

Sample Input 1:

1
()()())

Sample Output 1:

Explanation Of Sample Input 1:

Test case 1:
For the first test case of sample output 1, three different strings can be created by removing one extra parenthesis.

Sample Input 2:

2
()(()
()()()

Sample Output 2:

1
1

Explanation Of Sample Input 2:

Test case 1:
For the first test case of sample output 2, we can remove the middle parenthesis to get string ()().

Test case 2:   
For the second test case of sample output 2, as the string is already balanced, hence we can return the original string.

Approaches (1)

Approach 1

Greedy Approach

Time Complexity

Space Complexity

(100% EXP penalty)

Valley of depression

Console