Generate All Valid Strings

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’

For the first test case: All the valid unique strings that can be formed from “()())” are “()()”, ”()”, ”(())”, ” ” among which “()()”, “(())” are formed from only 1 ‘)’ removal which is the minimum among all. For the second test case: All the valid unique strings that can be formed from “()(x))()” are “()(x)()”, ”()()”, ”(())”, ”((x))”, ”(x)”, ”(x)()”, ”((x))()”, ” ” among which ”((x))()” and “()(x)()” are formed from only 1 ‘)’ removal at index 1 and 5 respectively which takes the minimum removals among all possible valid strings.

For the first test case: All the valid unique strings that can be formed from “))a((” are “a” and “” (empty string is also a valid string) in which “a” is formed from 2 ‘)’ removals at index 0 and 1 and 2 ‘(’ removal at index 3 and 4. which is the minimum among all possible valid strings. For the second test case: All the valid unique strings that can be formed from “ (()s())” are “()(s)()”, ”((())”, ”(s)”, ”(()s)”, ”(s())”, ”(()s())”, ” ”, ”s”, ”((s)), "()s()” among which "(()s())” is formed from 0 removals which is the minimum possible removals.

Using BFS

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’.

Time Complexity

O(|STR|*2^|STR|), where |STR| is the length of the string 'STR’.

Because in the worst case for every index we are removing the character at that index and inserting the remaining string into the queue. Then, for each string inside the queue we are checking if the string is valid or not which takes O(|STR|) time.

Space Complexity

O(|STR|*|STR|), where |STR| is the length of the string 'STR’.

Because in the worst case the queue will contain all possible unique substrings formed from ‘STR’ and all these substrings are also mapped in the hash table.

Problem statement

Sample Input 1 :

Sample Output 1 :

Explanation for Sample Output 1 :

Sample Input 2 :

Sample Output 2 :

Explanation for Sample Output 2 :