Remove Invalid Parentheses

Remove Invalid Parentheses

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

Example 1:

Input: "()())()"
Output: ["()()()", "(())()"]

Example 2:

Input: "(a)())()"
Output: ["(a)()()", "(a())()"]

Example 3:

Input: ")("
Output: [""]

 class Solution {

public:

    int find1stInvalidindex(string s,string flag)

    {

        int open=0;

         for(int i=0;i<s.size();++i)

        {

            if(s[i]==flag[0])

            {

                ++open;

            }else if(s[i]==flag[1])

            {

                --open;

            }

             if(open<0)

                 return i;

        }

        return -1;

    }

    void remove(string s,int pos,vector<string> &res,string flag)

    {

        int idx=find1stInvalidindex(s,flag);

        if(idx==-1)

        {

            reverse(s.begin(),s.end());

            if(flag[0]=='(')

                remove(s,0,res,")(");

            else

                res.push_back(s);

            return;

        }

        for(int i=pos;i<=idx;++i)

        {

            if(s[i]!=flag[1])continue;

            if(pos!=i&&s[i-1]==flag[1])continue;

            remove(s.substr(0,i)+s.substr(i+1),i,res,flag);

        }

    }

    vector<string> removeInvalidParentheses(string s) {

        vector<string> ans;

       remove(s,0,ans,"()");

        return ans;  

    }

};