Leetcode 301 Solution

class Solution {
public:
    bool isvalid(const string& s)
    {
        int cnt = 0;
        
        for (auto ch : s)
        {
            if (ch == '(')
                cnt++;
            else if (ch == ')')
                cnt--;
            
            if (cnt < 0)
                return false;
        }
        
        return cnt == 0;
    }
    vector<string> removeInvalidParentheses(string s) {
        queue<string> q;
        unordered_set<string> visited;
        vector<string> res;
        bool found = false;
        
        q.push(s);
        visited.insert(s);
        
        while (q.empty() == false)
        {
            auto str = q.front();
            q.pop();
            
            if (isvalid(str))
            {
                res.push_back(str);
                found = true;
            }
            
            if (found)
                continue;
            
            for (int i = 0; i < str.size(); i++)
            {
                if (str[i] == '(' || str[i] == ')')
                {
                    string next_str = str.substr(0, i) + str.substr(i + 1);
                    
                    if (visited.find(next_str) != visited.end())
                        continue;
                    
                    visited.insert(next_str);
                    q.push(next_str);
                }
            }
        }
        
        return res;
    }
};