Generate All Valid Strings

Posted: 16 Feb, 2021
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

Ninja has been given a string ‘STR’ containing ‘(‘ and ‘)’. ‘STR’ may also contain lower case alphabets. In order to make ‘STR’ valid Ninja can remove either ‘)’ or ‘(’ from ‘STR’.

Here are some examples of valid ‘STR’ “((a))”, “(g)()”, “(())()”, "" (an empty string is also a valid string).

Ninja wants to know all the possible valid strings that can be formed from ‘STR’ by minimum possible removals (possibly zero).

Can you help Ninja to generate all valid strings from ‘STR’ by minimum removals?

For Example :
For the given ‘STR’ =  “()(()”, we can form a valid string “()()” by removing ‘(‘ at index 2 or 3.
Input Format :
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first and the only line of each test case contains a string ‘STR’
Output Format :
For each test case, print all possible unique valid strings that can be formed from ‘STR’ in a separate line.

Print the output of each test case in a separate line.
Note :
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints :
1 <= ‘T’ <= 100
‘STR[i]’ = ‘(‘, ‘)’ or Lower case english alphabet
1 <= |STR| <= 2000

Where |STR| denotes the length of the given string.

Time Limit: 1 sec
Approach 1

We are having three challenges in this problem: removing minimum parenthesis, generating valid strings and without any duplicates. We can solve this problem by using BFS because BFS guarantees the shortest path. Since the problem is to remove minimum parenthesis, we can think of using BFS. A straightforward approach is to remove a parenthesis from the current string until we get a valid string. It generates both duplicate and invalid strings. We can use a hash table to remove duplicates and check each string for validity.

 

Algorithm

 

We create a queue of type string for BFS, a hashmap of type string to handle the duplicates, and an array/list to store our final result. First, insert the given string ‘STR’ into the queue and do the following while the queue does not get empty.

  • Pop the string from the queue and check whether this string is already processed or not i.e. if this is present in the hash map or not. If it is already present then do nothing. If not present then insert it in the hash map.
  • Check if this string is a valid string or not. If the string is valid then insert it in our ‘answer’ array/list. We will call out helper function ‘isvalidto check whether the string is valid or not which is defined as follows:
    • Initialize a variable ‘counter’ to 0.
    • Iterate the string and for each index do the following:
      • If the element is ‘(‘ then increase the ‘counter by 1.
      • If the element is ‘)’ then decrease the ‘counter’ by 1.
      • If at any index the value of the counter becomes negative then return false (not a valid string).
    • Return true (string is a valid string)
  • If the string is not valid and if the ‘answer’ array/list is not empty then iterate the string and for each index do the following:
    • If the element at index ‘i’ is ‘)’ or ‘(’, then remove this element and insert the remaining string.
  • Finally, return ‘answer’.
Try Problem