Remove Invalid Parentheses
You are given a string consisting only of parentheses and letters. Your task is to remove the minimum number of invalid parentheses and return all possible unique, valid strings thus obtained.

Note:

1) A string is valid only if every left parenthesis has corresponding right parentheses in the same order. For example Given ‘STR’ = (())()) is not a valid string, whereas ‘STR’ = (())() is a valid string.

Input Format

The first line of input contains an integer 'T' representing the number of test cases. The first and the only line of each test case contains a single string ‘STR’ representing the parenthesis.

Output Format:

For each test case, return all possible unique, valid strings after removing the minimum number of parentheses. The output of each test case will be printed 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

Question

Remove Invalid Parentheses

You are given a string consisting only of parentheses and letters. Your task is to remove the minimum number of invalid parentheses and return all possible unique, valid strings thus obtained.

Note:

1) A string is valid only if every left parenthesis has corresponding right parentheses in the same order.

For example Given ‘STR’ = (())()) is not a valid string, whereas ‘STR’ = (())() is a valid string.

Input Format

The first line of input contains an integer 'T' representing the number of test cases.

The first and the only line of each test case contains a single string ‘STR’ representing the parenthesis.

Output Format:

For each test case, return all possible unique, valid strings after removing the minimum number of parentheses. 

The output of each test case will be printed 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 <= 5
1 <= |STR| <= 50

Time Limit: 1 second

Accepted Answer

Breadth First Search

The idea here is to use the BFS algorithm. Using BFS, we will move through states level by the level that will ensure the removal of the minimal number of parentheses. At each level, we will remove only one parenthesis. So, if we found a valid string, we will restrict ourselves to that level only.

Please note that the overhead to pass parameters in a recursive call is also avoided because of BFS.

Algorithm:

Declare a hash set, ‘VISTED’ to keep track of the visited strings.
Declare a vector of string, ‘RESULT’ to store the final result.
Declare a queue of string, ‘Q’ for level order traversal.
Declare a bool variable, ‘VALID’ (initially false), that will account for the validity of the string at a level.
Push the string, ‘STR’ in the queue, and insert in ‘visited’ (to mark it as visited).
Run the loop while ‘Q’ is not empty
- Declare a string, ‘POSSIBLE_ANSWER’, and store the front value of ‘Q’ in it.
- Pass ‘POSSIBLE_ANSWER’ to the ‘IS_VALID_STRING’ function, where ‘IS_VALID_STRING’ checks whether the string has valid parentheses and check if ‘POSSIBLE_ANSWER’ is valid. If valid, insert the ‘POSSIBLE_ANSWER’ in ‘RESULT’ and update the ‘VALID’ to be true.
- If VALID == true, that shows that string at this level will appear in the output. So, skip the remaining part and continue the iteration.
- Otherwise, run a loop from i = 0 to ‘N’. Here ‘N’ is the length of the string, ‘POSSIBLE_ANSWER’.
If POSSIBLE_ANSWER[i] == ‘)’ or POSSIBLE_ANSWER == ‘(‘ shows that current character is a parenthesis. So, put the string after removing the current character in a string, ‘TEMP’.
1. If VISITED.COUNT(TEMP) == 0 shows that ‘TEMP’ is not visited. So, push ‘TEMP’ in ‘Q’ and mark it visited.
Return the ’RESULT’.

Description of ‘IS_VALID_STRING’ function

This function will take one parameter :

STR: A string variable to store the original string.

bool IS_VALID_STRING(STR) :

Declare three integer variables:
- LEFT: Stores the number of left parentheses at any instant
- RIGHT: Stores the number of right parentheses at any instant
- INDEX: An integer variable to iterate over the string
Run a loop while INDEX < STR.LENGTH()
- If STR[INDEX] == ‘(‘ that shows that the current index is a left parenthesis. So, increment the variable ‘LEFT’.
- Else if STR[INDEX] == ‘)’ shows that the current index is a right parenthesis. Then, we will check:
  - If LEFT > 0, that shows there is left parenthesis already present. So, we decrement the variable ‘LEFT’ to nullify the effect of the right parenthesis.
  - Else, it implies that there isn’t any left parenthesis. So, increment the variable ‘RIGHT’.
  - If RIGHT > LEFT, that shows that at this instant, the number of right parentheses has become greater than the number of left parentheses. So, the string ‘STR’ can never be valid. Therefore, return false.
- Increment the index.
Return LEFT == RIGHT. So, true is returned if both are equal otherwise, false.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of parentheses in the string.

We are using a queue that can take O(N) space in the worst case.

Time Complexity: OtherExplanation:

O(N * (2 ^ N - 1)), where ‘N’ is the number of parentheses in the string.

Checking whether a string is valid or not will take O(N) time at each level. And, for every string of length N, we will have (N - 1) strings at the next level, i.e., C(N, N - 1) at the second level, C(N, N-2) at the third level, and so on.

Therefore, total time = N * C(N, N) + (N - 1) * C(N, N - 1) + (N - 2) * C(N, N - 2) + . . . + 1 * C(N, 1) = N * (2 ^ (N - 1)).

Python (3.5)

'''
    Time Complexity  :   O(N * (2 ^ N))
    Space Complexity :   O(N)

    Where N is the number of parentheses in the string.
'''

from collections import deque

def isValidString(string):
    left = 0
    right = 0
    index = 0
    
    while index < len(string):
        if string[index] == '(':
            left += 1
            
        elif string[index] == ')':
            if left > 0:
                left -= 1
                
            else:
                right += 1
                
            if right > left:
                return False
                
        index += 1
        
    return left == right
    
def removeInvalidParentheses(string):
    
    visited = set()
    result = []
    q = deque()
    valid = False
    
    visited.add(string)
    q.append(string)
    # BFS.
    while len(q) > 0:
        possibleAnswer = q.popleft()
        
        # Check whether 'possibleAnswer' is valid or not.
        if isValidString(possibleAnswer):
            result.append(possibleAnswer)
            valid = True
            
        # If true, then the solution exists at current level. No need to move at next state.
        if valid == True:
            continue
        
        # Generate all possible next state of Strings from current String.
        for i in range(len(possibleAnswer)):
            if possibleAnswer[i] == '(' or possibleAnswer[i] == ')':
                temp = possibleAnswer[0 : i] + possibleAnswer[i + 1 : len(possibleAnswer)]
                
                if temp not in visited:
                    q.append(temp)
                    visited.add(temp)
                    
    return sorted(result)

C++ (g++ 5.4)

/*

    Time Complexity  :   O(N * (2 ^ N))

    Space Complexity :   O(N)



    Where N is the number of parentheses in the string.

*/



#include 

#include 



// Function to check whether a string has valid parentheses or not.

bool isValidString(string &str)

{

    int left = 0, right = 0, index = 0;

    while (index < str.length())

    {

        if (str[index] == '(')

        {

            left++;

        }

        else if (str[index] == ')')

        {

            if (left > 0)

            {

                left--;

            }

            else

            {

                right++;

            }

            if (right > left)

            {

                return false;

            }

        }

            index++;

    }

        return left == right;

}

    

vector removeInvalidParentheses(string &str)

{

    unordered_set visited;

    vector result;

    queue q;

    bool valid = false;

        

    visited.insert(str);

    q.push(str);

        

    // BFS

    while (q.empty() == false)

    {

        string possibleAnswer = q.front();

        q.pop();



        // Check whether 'possibleAnswer' is valid or not.

        if (isValidString(possibleAnswer))

        {

            result.push_back(possibleAnswer);

            valid = true;

        }

        

        // If true, then the solution exists at current level. No need to move at next state.

        if (valid == true)

        {

            continue;

        }

        

        // Generate all possible next state of strings from current string.

        for (int i = 0; i < possibleAnswer.length(); i++)

        {

            if (possibleAnswer[i] == '(' || possibleAnswer[i] == ')')

            {

                string temp = (possibleAnswer.substr(0, i)).append(possibleAnswer.substr(i + 1));

                

                if (visited.count(temp) == 0)

                {

                    q.push(temp);

                    visited.insert(temp);

                }

            }

        }

    }

    return result;

}

Java (SE 1.8)

/*
    Time Complexity  :   O(N * (2 ^ N))
    Space Complexity :   O(N)

    Where N is the number of parentheses in the string.
*/

import java.util.HashSet;
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;

public class Solution {
	
	// Function to check whether a String has valid parentheses or not
	public static boolean isValidString(String str) {
		int left = 0, right = 0, index = 0;
		while (index < str.length()) {
			if (str.charAt(index) == '(') {
				left++;
			} else if (str.charAt(index) == ')') {
				if (left > 0) {
					left--;
				} else {
					right++;
				}
				if (right > left) {
					return false;
				}
			}
			index++;
		}
		return left == right;
	}

	public static ArrayList removeInvalidParentheses(String str) {
		HashSet visited = new HashSet<>();
		ArrayList result = new ArrayList<>();
		Queue q = new LinkedList<>();
		boolean valid = false;

		visited.add(str);
		q.add(str);

		// BFS
		while (q.isEmpty() == false) {
			String possibleAnswer = q.peek();
			q.remove();

			// Check whether 'possibleAnswer' is valid or not
			if (isValidString(possibleAnswer)) {
				result.add(possibleAnswer);
				valid = true;
			}

			// If true, then the solution exists at current level. No need to move at next
			// state.
			if (valid == true) {
				continue;
			}

			// Generate all possible next state of Strings from current String
			for (int i = 0; i < possibleAnswer.length(); i++) {
				if (possibleAnswer.charAt(i) == '(' || possibleAnswer.charAt(i) == ')') {
					String temp = (possibleAnswer.substring(0, i)) + (possibleAnswer.substring(i + 1));

					if (!visited.contains(temp)) {
						q.add(temp);
						visited.add(temp);
					}
				}
			}
		}
		return result;
	}
}

Accepted Answer

Recursion & Backtracking

The idea is to explore all the possibilities by keeping two options for each parenthesis, i.e., to include or exclude. This provides us with a thought to use recursion and backtracking to solve this problem.

To check for a valid string, we will maintain the count of left and right parentheses. At any instant, if the number of left parentheses is equal to the number of right parentheses, then the string is valid; otherwise, not.

We should also keep in mind that if the number of right parentheses is greater than the number of left parentheses, then the string can never be valid. At that instant, we do not need to recur forward.

For keeping track of unique strings, we will use a hash set (i.e., unordered_set in c++).

Algorithm:

Declare a global integer variable, ‘MIN_REMOVAL’, that will hold the minimum removals till now. Locally initialize it to INT_MAX.
Declare a hash set of strings, ‘HASH_SET’, to store all the unique, valid strings.
Declare a string, ‘RESULT_SO_FAR’, to store the temporary result.
Call the ‘REMOVE_RECURSIVELY’ function to get the list of valid unique strings in ‘HASH_SET’.
Declare a vector of strings, ‘RESULT’ to store the final result.
Iterate over the ‘HASH_SET’ and store every string in ‘RESULT’.
Return the ‘RESULT’.

Description of ‘REMOVE_RECURSIVELY’ function

This function will take seven parameters :

STR: A string variable to store the original string.
INDEX: An integer to keep track of the current index of the original string.
RESULT_SO_FAR: A string variable to store the temporary result.
LEFT_COUNT: An integer to keep track of the number of left parentheses.
RIGHT_COUNT: An integer to keep track of the number of right parentheses.
REMOVE_COUNT: An integer to keep track of the number of removals made so far.
HASH_SET: A hash set of strings to maintain unique, valid strings.

void REMOVE_RECURSIVELY(STR, INDEX, RESULT_SO_FAR, LEFT_COUNT, RIGHT_COUNT, REMOVE_COUNT, HASH_SET):

If INDEX == LENGTH of ‘STR’, that shows that we have tried all possible removals. So, we will check:
- If LEFT_COUNT == RIGHT_COUNT that shows we have found a valid string. So, we will check:
  - If REMOVE_COUNT <= MIN_REMOVAL that shows the ‘RESULT_SO_FAR” is the valid candidate for the result. So, we will check:
    1. If REMOVE_COUNT < MIN_REMOVAL shows that the ‘RESULT_SO_FAR’ is the valid string obtained with minimum removal. So, clear the ‘HASH_SET’ and update ‘MIN_REMOVAL’ by ‘REMOVE_COUNT’.
  - Insert ‘RESULT_SO_FAR’ in the HASH_SET.
Else
- Check if STR[INDEX] != ‘(‘ and STR[INDEX] != ‘)’ that shows that the character at current index is not a parenthesis. So, push the current character in ‘RESULT_SO_FAR’ and call ‘REMOVE_RECURSIVELY’ function by updating INDEX to INDEX + 1. On returning back, pop the last inserted character.
- Else, we will now explore both options, i.e., to include the current character or exclude the current character.
  - Include the current character in ‘RESULT_SO_FAR’.
  - If S[INDEX] == ‘(‘ that shows that the current character is a left parenthesis. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘LEFT_COUNT’ to ‘LEFT_COUNT + 1’.
  - Else current character is a right parenthesis. So, check if RIGHT_COUNT < LEFT_COUNT shows that a valid string can be found in future. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘RIGHT_COUNT’ to ‘RIGHT_COUNT + 1’.
  - Exclude the current character from ‘RESULT_SO_FAR’ and call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘REMOVE_COUNT’ to ‘REMOVE_COUNT + 1’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of parentheses in the string.

Our ‘removeRecursively’ function requires O(N) space in the form of recursive stack space.

Time Complexity: O(2^n)Explanation:

O(2 ^ N), where ‘N’ is the number of parentheses in the string.

For every parenthesis, we have two choices: include or exclude. So, in the worst case, we can have only left parentheses in the string, which will lead to O(2 ^ N) time complexity.

Python (3.5)

'''

    Time Complexity  :   O(2 ^ N)

    Space Complexity :   O(N)



    Where N is the number of parentheses in the string.

'''



import sys



minRemoval = 0



def removeRecursively(string, index, resultSoFar, leftCount, rightCount, removeCount, hashSet):

    global minRemoval

    # Base Case.

    if index == len(string):

        

        # Valid String is found.

        if leftCount == rightCount:

            

            if removeCount <= minRemoval:

                

                if removeCount < minRemoval:

                    

                    hashSet.clear()

                    minRemoval = removeCount

                    

                hashSet.add(resultSoFar)

                

                

    else:

        # If current character is not parenthesis, include it in 'possibleAnswer'.

        if string[index] != '(' and string[index] != ')':

            

            resultSoFar += string[index]

            removeRecursively(string, index + 1, resultSoFar, leftCount, rightCount, removeCount, hashSet)

            

            # Remove last character.

            resultSoFar = resultSoFar[0 : len(resultSoFar) - 1]

            

        else:

            # For parenthesis, two cases: Include or Exclude.

            resultSoFar += string[index]

            # Include case.

            if string[index] == '(':

                removeRecursively(string, index + 1, resultSoFar, leftCount + 1, rightCount, removeCount, hashSet)

            elif leftCount > rightCount:

                removeRecursively(string, index + 1, resultSoFar, leftCount, rightCount + 1, removeCount, hashSet)

                

            # Remove last character.

            resultSoFar = resultSoFar[0 : len(resultSoFar) - 1]

            

            # Exclude case.

            removeRecursively(string, index + 1, resultSoFar, leftCount, rightCount, removeCount + 1, hashSet)

            



def removeInvalidParentheses(string):

    global minRemoval

    minRemoval = sys.maxsize

    hashSet = set()

    resultSoFar = ""

    

    # Generate all unique, valid Strings of maximum length and store in 'hashSet'.

    removeRecursively(string, 0, resultSoFar, 0, 0, 0, hashSet)

    

    result = []

    

    for answer in hashSet:

        result.append(answer)

        

    return sorted(result)

C++ (g++ 5.4)

/*

    Time Complexity  :   O(2 ^ N)

    Space Complexity :   O(N)



    Where N is the number of parentheses in the string.

*/



#include 

#include 



int minRemoval;



// Function to find all unique, valid strings of maximum length.

void removeRecursively(string str, int index, string &resultSoFar, int leftCount, int rightCount, int removeCount, unordered_set &hashSet)

{

    // Base case.

    if (index == str.length())

    {

        // Valid string is found.

        if (leftCount == rightCount)

        {

            if (removeCount <= minRemoval)

            {

                if (removeCount < minRemoval)

                {

                    hashSet.clear();

                    minRemoval = removeCount;

                }

                hashSet.insert(resultSoFar);

            }

        }

    }

    else

    {   

        // If current character is not parenthesis, include it in 'possibleAnswer'.

        if (str[index] != '(' && str[index] != ')')

        {

            resultSoFar.push_back(str[index]);

            removeRecursively(str, index + 1, resultSoFar, leftCount, rightCount, removeCount, hashSet);

            resultSoFar.pop_back();

        }

        else

        // For parenthesis, two cases: Include or Exclude.

        {

            // Include Case.

            resultSoFar.push_back(str[index]);

            if (str[index] == '(')

            {

                removeRecursively(str, index + 1, resultSoFar, leftCount + 1, rightCount, removeCount, hashSet);

            }

            else if (leftCount > rightCount)

            {

                removeRecursively(str, index + 1, resultSoFar, leftCount, rightCount + 1, removeCount, hashSet);

            }

            resultSoFar.pop_back();



            // Exclude Case.

            removeRecursively(str, index + 1, resultSoFar, leftCount, rightCount, removeCount + 1, hashSet);

        }

            

    }

}



vector removeInvalidParentheses(string &str)

{

    minRemoval = INT_MAX;



    unordered_set hashSet;

    string resultSoFar;



    // Generate all unique, valid strings of maximum length and store in 'hashSet'.

    removeRecursively(str, 0, resultSoFar, 0, 0, 0, hashSet);



    vector result;

    for (string answer : hashSet)

    {

        result.push_back(answer);

    }

    return result;

}

Java (SE 1.8)

/*
    Time Complexity  :   O(2 ^ N)
    Space Complexity :   O(N)

    Where N is the number of parentheses in the string.
*/

import java.util.HashSet;
import java.util.ArrayList;

public class Solution {
	static int minRemoval;

	// Function to find all unique, valid Strings of maximum length.
	public static void removeRecursively(String str, int index, String resultSoFar, int leftCount, int rightCount,
			int removeCount, HashSet hashSet) {
		// Base case.
		if (index == str.length()) {
			// Valid String is found.
			if (leftCount == rightCount) {
				if (removeCount <= minRemoval) {
					if (removeCount < minRemoval) {
						hashSet.clear();
						minRemoval = removeCount;
					}
					hashSet.add(resultSoFar);
				}
			}
		} else {

			// If current character is not parenthesis, include it in 'possibleAnswer'.
			if (str.charAt(index) != '(' && str.charAt(index) != ')') {
				resultSoFar += (str.charAt(index));
				removeRecursively(str, index + 1, resultSoFar, leftCount, rightCount, removeCount, hashSet);
				
				// Remove last character
				resultSoFar = resultSoFar.substring(0, resultSoFar.length() - 1);
			} else
			// For parenthesis, two cases: Include or Exclude
			{
				// Include Case.
				resultSoFar += (str.charAt(index));
				if (str.charAt(index) == '(') {
					removeRecursively(str, index + 1, resultSoFar, leftCount + 1, rightCount, removeCount, hashSet);
				} else if (leftCount > rightCount) {
					removeRecursively(str, index + 1, resultSoFar, leftCount, rightCount + 1, removeCount, hashSet);
				}
				
				// Remove last character.
				resultSoFar = resultSoFar.substring(0, resultSoFar.length() - 1);

				// Exclude Case.
				removeRecursively(str, index + 1, resultSoFar, leftCount, rightCount, removeCount + 1, hashSet);
			}

		}
	}

	public static ArrayList removeInvalidParentheses(String str) {
		minRemoval = Integer.MAX_VALUE;

		HashSet hashSet = new HashSet<>();
		String resultSoFar = "";

		// Generate all unique, valid Strings of maximum length and store in 'hashSet'.
		removeRecursively(str, 0, resultSoFar, 0, 0, 0, hashSet);

		ArrayList result = new ArrayList<>();
		for (String answer : hashSet) {
			result.add(answer);
		}
		return result;
	}
}

Accepted Answer

Optimized Backtracking

The idea here is to determine the number of left and right misplaced parentheses. After that, we no longer need to check for the global minimum and update the hash set. We can be sure that if the count of both left and right misplaced parentheses reduces to zero, then the string is valid and of maximum length (formed by minimum removals).

The optimized backtracking approach will be similar to approach 1 with some modifications.

Algorithm:

Declare three integer variables:
- LEFT_MISPLACED: Stores the number of misplaced left parentheses
- RIGHT_MISPLACED: Stores the number of misplaced right parentheses
- INDEX: An integer variable to iterate over the string
Run a loop while INDEX < STR.LENGTH()
- If STR[INDEX] == ‘(‘ that shows that the current index is a left parenthesis. So, increment the variable ‘LEFT_MISPLACED’.
- Else if STR[INDEX] == ‘)’ that shows that the current index is a right parentheses. Then, we will check:
  - If LEFT_MISPLACED > 0, that shows there is a misplaced left parentheses. So, we decrement the variable ‘LEFT_MISPLACED’ to nullify the effect of the right parenthesis.
  - Else, it implies that there isn’t any misplaced left parenthesis. So, increment the variable ‘RIGHT_MISPLACED’.
- Increment the index.
Declare a hash set of strings, ‘HASH_SET’, to store all the unique, valid strings.
Declare a string, ‘RESULT_SO_FAR’, to store the temporary result.
Call the ‘REMOVE_RECURSIVELY’ function to get the list of valid unique strings in ‘HASH_SET’.
Declare a vector of strings, ‘result’ to store the final result.
Iterate over the ‘HASH_SET’ and store every string in ‘RESULT’.
Return the ‘RESULT’.

Description of ‘REMOVE_RECURSIVELY’ function

This function will take eight parameters :

STR: A string variable to store the original string.
INDEX: An integer to keep track of the current index of the original string.
RESULT_SO_FAR: A string variable to store the temporary result.
LEFT_MISPLACED: An integer to keep track of the number of misplaced left parenthesis.
RIGHT_MISPLACED: An integer to keep track of the number of misplaced right parenthesis.
LEFT_COUNT: An integer to keep track of the number of left parentheses.
RIGHT_COUNT: An integer to keep track of the number of right parentheses.
HASH_SET: An unordered_set of strings to maintain unique, valid strings.

void REMOVE_RECURSIVELY(STR, INDEX, RESULT_SO_FAR, LEFT_MISPLACED, RIGHT_MISPLACED, LEFT_COUNT, RIGHT_COUNT, HASH_SET):

If INDEX == LENGTH of ‘STR’, that shows that we have tried all possible removals. So, we will check:
- If LEFT_MISPLACED == 0 and RIGHT_MISPLACED == 0 that shows we have found a valid string with minimum removals. So, insert ‘RESULT_SO_FAR’ in the ‘HASH_SET’ and return.
If STR[INDEX] != ‘(‘ and STR[INDEX] != ‘)’ that shows that the character at the current index is not a parenthesis. So, push the current character in ‘RESULT_SO_FAR’ and call ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’. On returning, remove the last added character.
Else, we will now explore both options, i.e., to include the current character or exclude the current character.
- Include the current character in ‘RESULT_SO_FAR’.
- If STR[INDEX] == ‘(‘ that shows that current character is a left parenthesis. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘LEFT_COUNT’ to ‘LEFT_COUNT + 1’.
- Else current character is a right parenthesis. So, check if RIGHT_COUNT < LEFT_COUNT shows that a valid string can be found in future. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘RIGHT_COUNT’ to ‘RIGHT_COUNT + 1’.
- Exclude the current character from ‘RESULT_SO_FAR’.
- If STR[INDEX] == ‘(‘ and LEFT_MISPLACED > 0 that shows the current left parenthesis can be excluded. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘LEFT_MISPLACED’ to ‘LEFT_MISPLACED - 1’.
- Else if STR[INDEX] == ‘)‘ and RIGHT_MISPLACED > 0 that shows the current right parenthesis can be excluded. So, call the ‘REMOVE_RECURSIVELY’ function by updating ‘INDEX’ to ‘INDEX + 1’ and ‘RIGHT_MISPLACED’ to ‘RIGHT_MISPLACED - 1’.

Space Complexity: O(n)Explanation:

O(N), where ‘N’ is the number of parentheses in the string.

Our ‘REMOVE_RECURSIVELY’ function requires O(N) space in the form of recursive stack space.

Time Complexity: O(2^n)Explanation:

O(2 ^ N), where ‘N’ is the number of parentheses in the string.

The complexity is greatly improved. But asymptotically, it is still the same as the previous approach because in the worst case, we can have only the left parenthesis in the string. In that case, the number of misplaced left parenthesis will be equal to N resulting in two options: include or exclude. Consequently, time complexity will be O(2 ^ N).

Python (3.5)

'''
    Time Complexity  :   O(2 ^ N)
    Space Complexity :   O(N)

    Where N is the number of parentheses in the string.
'''

def removeRecursively(string, index, resultSoFar, leftMisplaced, rightMisplaced, leftCount, rightCount, hashSet):
    # Base case.
    if index == len(string):
        # Valid String is found.
        if leftMisplaced == 0 and rightMisplaced == 0:
            hashSet.add(resultSoFar)
            
        return
    
    # If current character is not parenthesis, include it in 'possibleAnswer'.
    if string[index] != '(' and string[index] != ')':
        resultSoFar += (string[index])
        
        removeRecursively(string, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount, rightCount, hashSet)
        
        # Remove last character.
        resultSoFar = resultSoFar[0 : len(resultSoFar) - 1]
    # For parenthesis, two cases: Include or Exclude.
    else:
        resultSoFar += (string[index])
        
        if string[index] == '(':
            removeRecursively(string, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount + 1, rightCount, hashSet)
        
        elif leftCount > rightCount:
            removeRecursively(string, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount, rightCount + 1, hashSet)
            
        # Exclude Case.
        resultSoFar = resultSoFar[0 : len(resultSoFar) - 1]
        
        if string[index] == '(' and leftMisplaced > 0:
            removeRecursively(string, index + 1, resultSoFar, leftMisplaced - 1, rightMisplaced, leftCount, rightCount, hashSet)
            
        elif string[index] == ')' and rightMisplaced > 0:
            removeRecursively(string, index + 1, resultSoFar, leftMisplaced, rightMisplaced - 1, leftCount, rightCount, hashSet)


def removeInvalidParentheses(string):
    leftMisplaced = 0
    rightMisplaced = 0
    index = 0
    
    # Count number of misplaced left and right parentheses.
    while index < len(string):
        if string[index] == '(':
            leftMisplaced += 1
        elif string[index] == ')':
            if leftMisplaced > 0:
                leftMisplaced -= 1
            else:
                rightMisplaced += 1
                
        index += 1
        
    hashSet = set()
    
    resultSoFar = ""
    
    # Generate all unique, valid Strings of maximum length and store in 'hashSet'.
    removeRecursively(string, 0, resultSoFar, leftMisplaced, rightMisplaced, 0, 0, hashSet)
    
    result = []
    for st in hashSet:
        result.append(st)
        
    return sorted(result)

C++ (g++ 5.4)

/*

    Time Complexity  :   O(2 ^ N)

    Space Complexity :   O(N)



    Where N is the number of parentheses in the string.

*/



#include 



// Function to find all unique, valid strings of maximum length.

void removeRecursively(string &str, int index, string &resultSoFar, int leftMisplaced, int rightMisplaced, int leftCount, int rightCount, unordered_set &hashSet)

{

    // Base Case

    if (index == str.length())

    {

        // Valid string is found.

        if (leftMisplaced == 0 && rightMisplaced == 0)

        {

            hashSet.insert(resultSoFar);

        }

        return;

    }

    

    // If current character is not parenthesis, include it in 'possibleAnswer'.

    if (str[index] != '(' && str[index] != ')')

    {

        resultSoFar.push_back(str[index]);

        removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount, rightCount, hashSet);

        resultSoFar.pop_back();

    }

    // For parenthesis, two cases: Include or Exclude.

    else

    {

        // Include Case.

        resultSoFar.push_back(str[index]);

        

        if (str[index] == '(')

        {

            removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount + 1, rightCount, hashSet);

        }

        else if (leftCount > rightCount)

        {

            removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount, rightCount + 1, hashSet);

        }

        

        // Exclude Case.

        resultSoFar.pop_back();

            

        if (str[index] == '(' && leftMisplaced > 0)

        {

            removeRecursively(str, index + 1, resultSoFar, leftMisplaced - 1, rightMisplaced, leftCount, rightCount, hashSet);

        }

        else if (str[index] == ')' && rightMisplaced > 0)

        {

            removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced - 1, leftCount, rightCount, hashSet);

        }

    }

}



vector removeInvalidParentheses(string &str)

{

    int leftMisplaced = 0, rightMisplaced = 0, index = 0;

    

    // Count number of misplaced left and right parentheses.

    while (index < str.length())

    {

        if (str[index] == '(')

        {

            leftMisplaced++;

        }

        else if (str[index] == ')')

        {

            if (leftMisplaced > 0)

            {

                leftMisplaced--;

            }

            else

            {

                rightMisplaced++;

            }

        }

        index++;

    }

        

    unordered_set hashSet;

    string resultSoFar;

    

    // Generate all unique, valid strings of maximum length and store in 'hashSet'.

    removeRecursively(str, 0, resultSoFar, leftMisplaced, rightMisplaced, 0, 0, hashSet);

        

    vector result;

    for (string str : hashSet)

    {

        result.push_back(str);

    }

    return result;

}

Java (SE 1.8)

/*

    Time Complexity  :   O(2 ^ N)

    Space Complexity :   O(N)



    Where N is the number of parentheses in the string.

*/



import java.util.HashSet;

import java.util.ArrayList;



public class Solution {

	// Function to find all unique, valid Strings of maximum length.

	public static void removeRecursively(String str, int index, String resultSoFar, int leftMisplaced,

			int rightMisplaced, int leftCount, int rightCount, HashSet hashSet) {

		// Base Case.

		if (index == str.length()) {

			// Valid String is found.

			if (leftMisplaced == 0 && rightMisplaced == 0) {

				hashSet.add(resultSoFar);

			}

			return;

		}



		// If current character is not parenthesis, include it in 'possibleAnswer'.

		if (str.charAt(index) != '(' && str.charAt(index) != ')') {

			resultSoFar += (str.charAt(index));

			removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount, rightCount,

					hashSet);

			

			// Remove last character.

			resultSoFar = resultSoFar.substring(0, resultSoFar.length() - 1);

		}

		// For parenthesis, two cases: Include or Exclude.

		else {

			// Include Case.

			resultSoFar += (str.charAt(index));



			if (str.charAt(index) == '(') {

				removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount + 1, rightCount,

						hashSet);

			} else if (leftCount > rightCount) {

				removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced, leftCount, rightCount + 1,

						hashSet);

			}



			// Exclude Case.

			resultSoFar = resultSoFar.substring(0, resultSoFar.length() - 1);



			if (str.charAt(index) == '(' && leftMisplaced > 0) {

				removeRecursively(str, index + 1, resultSoFar, leftMisplaced - 1, rightMisplaced, leftCount, rightCount,

						hashSet);

			} else if (str.charAt(index) == ')' && rightMisplaced > 0) {

				removeRecursively(str, index + 1, resultSoFar, leftMisplaced, rightMisplaced - 1, leftCount, rightCount,

						hashSet);

			}

		}

	}



	public static ArrayList removeInvalidParentheses(String str) {

		int leftMisplaced = 0, rightMisplaced = 0, index = 0;



		// Count number of misplaced left and right parentheses.

		while (index < str.length()) {

			if (str.charAt(index) == '(') {

				leftMisplaced++;

			} else if (str.charAt(index) == ')') {

				if (leftMisplaced > 0) {

					leftMisplaced--;

				} else {

					rightMisplaced++;

				}

			}

			index++;

		}



		HashSet hashSet = new HashSet(); 



		String resultSoFar = "";



		// Generate all unique, valid Strings of maximum length and store in 'hashSet'.

		removeRecursively(str, 0, resultSoFar, leftMisplaced, rightMisplaced, 0, 0, hashSet);



		ArrayList result = new ArrayList<>();

		for (String st : hashSet) {

			result.add(st);

		}

		return result;

	}

}

You are given a string consisting only of parentheses and letters. Your task is to remove the minimum number of invalid parentheses and return all possible unique, valid strings thus obtained.

Note:

Input Format

Output Format:

Note:

Constraints:

Top MAQ Software Software Engineer interview questions & answers

Popular interview questions of Software Engineer

Top HR questions asked in MAQ Software Software Engineer