Removing Invalid Parentheses - Leetcode Time Complexity

Question

I was solving this problem on leetcode and the problem statement is as follows.

Remove the minimum number of invalid parentheses in order to make the input string valid. Return all possible results.

Note: The input string may contain letters other than the parentheses ( and ).

Examples:
"()())()" -> ["()()()", "(())()"]
"(a)())()" -> ["(a)()()", "(a())()"]
")(" -> [""]

I was able to solve the problem after a while. But I'm not able to find the time complexity of my solution. My code is as follows. Please help me find the time complexity.

    class Solution {
public:

    void balance(string s, int curr_index, int changes, int max_changes, unordered_set<string> &memo, vector<string> &result){

        if(memo.find(s) != memo.end()){
            return;
        }

        if(changes == max_changes){
            int opening = 0;
            for(int i = 0; i < s.length(); i++){
                if(s[i] == '('){
                    opening++;
                }
                else if(s[i] == ')'){
                    if(opening == 0){
                        return;
                    }
                    else{
                        opening--;
                    }
                }
            }
            if(opening == 0){
                result.push_back(s);
            }
        }
        else if(changes > max_changes || curr_index >= s.length()){
            return;
        }
        else{
            if(s[curr_index] == '(' || s[curr_index] == ')'){
                string temp = s;
                temp.erase(temp.begin() + curr_index);
                balance(temp, curr_index, changes + 1, max_changes, memo, result);
            }

            balance(s, curr_index + 1, changes, max_changes, memo, result);
        }

        memo.insert(s);

    }


    vector<string> removeInvalidParentheses(string s) {

        int opening = 0;
        int min_changes = 0;

        vector<string> result;

        for(int i = 0; i < s.length(); i++){
            if(s[i] == ')' && opening == 0){
                min_changes++;
            }
            else if(s[i] == ')' && opening != 0){
                opening--;
            }
            else if(s[i] == '('){
                opening++;
            }
        }

        min_changes += opening;

        if(min_changes == s.length()){
            result.push_back("");
            return result;
        }
        else{

            unordered_set<string> memo;

            balance(s, 0, 0, min_changes, memo, result);

            return result;
        }

    }
    };

The time complexity for the above seems to be O(n!2^n). But you can actually improve it using the BFS solution for this question. Time complexity in that case comes to be around O(n!) — CodeHunter

kraskevich kraskevich · Accepted Answer · 2017-08-06T18:46:17

It's exponential. There's nothing you can do about because the output size may be exponential.

Consider the following example: (a(a(a(a.....)))))), where the number of pairs (a is twice the number of closing parenthesis. It's clear that we need to remove exactly half of the opening parenthesis, and it's also clear that removing any their subset yield a unique string.

Let the length of the string be 5n. Then we have 2n '(' and 'a' and n ')'. There are 2n choose n ways to remove a subset of opening parenthesis and get a valid string, which is an exponent in the length of the string.

Removing Invalid Parentheses - Leetcode Time Complexity

2 Answers