Generate All Valid Strings
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
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 ‘isvalid’ to 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’.
We have already discussed the function isValid in the previous approach in which we use a counter to check for a valid string. The counter will be incremented when it is ‘(‘ and decrease when it is ‘)’. Whenever the counter is negative, it means we are having more closing brackets ‘)’ than opening brackets '(‘ in the prefix string.
In order to make the prefix valid, we need to remove a ‘)’. Now the problem is which extra ‘)’ we should remove. At the first glance, it appears we can remove any extra ‘)’ in the prefix. However, it can generate duplicate results. For example: if ‘STR’ = “(a))”, we can remove either ‘STR[2]’ or ‘STR[3]’ but the result is the same “(a)”. Thus, we will try to remove the first ‘)’ in a series of consecutive ‘)’s.
After removal, the prefix string becomes valid. Then we will call the function recursively to solve the rest of the string. However, we need to keep track of the last removal position. If we do not have this position, we will end up generating duplicates by removing two ‘)’ in two steps only in a different order.
For this, we keep tracking the last removal position and only remove ‘)’ after that.
Now for strings “(“, “(()(()” in which we need to remove ‘(‘, we do the same from right to left. For this, we can reverse the string and reuse the code.
Here is the complete algorithm:
We will call our recursive function ‘removeBrackets’ which will have ‘STR’, ‘answer’ to store the final array/list of strings, ’curr_i’ to store the current index, a variable ‘counter’ which is initialized with 0 and ‘last_j’ to store the index of the last bracket removed. We will iterate through the ‘STR’ and for each index do the following.
Algorithm
- If the character at this index is ‘(‘ then increase ‘counter’ by 1 else decrease ‘counter’ by 1.
- If at any index the value to ‘counter’ becomes negative then do the following:
- Iterate the ‘STR’ from ‘last_j’ to the current index inclusive and for each index do the following:
- If the character at this index is ‘)’ and the current index is equal to ‘last_j’ or ‘STR[index - 1]' != ‘)’ then call the recursive function by removing the current character and passing the remaining string as an argument.
- Return from this if the value of ‘counter’ is negative.
- Iterate the ‘STR’ from ‘last_j’ to the current index inclusive and for each index do the following:
- Reverse the string and handle the following two cases :
- Is ‘STR[0]’ is ‘(’ call the recursive function to check from right to left as discussed above.
- Else add the ‘STR’ to our ‘answer’.
- Finally return ‘answer’.
