<p>Given a string <code>s</code> that contains parentheses and letters, remove the minimum number of invalid parentheses to make the input string valid.</p>

<p>Return <em>a list of <strong>unique strings</strong> that are valid with the minimum number of removals</em>. You may return the answer in <strong>any order</strong>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;()())()&quot;
<strong>Output:</strong> [&quot;(())()&quot;,&quot;()()()&quot;]
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;(a)())()&quot;
<strong>Output:</strong> [&quot;(a())()&quot;,&quot;(a)()()&quot;]
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;)(&quot;
<strong>Output:</strong> [&quot;&quot;]
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 25</code></li>
	<li><code>s</code> consists of lowercase English letters and parentheses <code>&#39;(&#39;</code> and <code>&#39;)&#39;</code>.</li>
	<li>There will be at most <code>20</code> parentheses in <code>s</code>.</li>
</ul>

class Solution {
    string remove_open(string_view s, int count)
    {
        vector<const char*> to_remove;
        string result;

        cout << "TO FIX OPEN: " << s << "," << count << endl; 

        for (auto start = rbegin(s); start != rend(s) && count; --count, ++start)
        {
            start = find(start, rend(s), '(');

            assert(start != rend(s));

            to_remove.push_back(&*start);
        }

        cout << "TO REMOVE OPEN: " << to_remove.size() << endl; 

        auto start = begin(s);
        for (auto it = to_remove.rbegin(); it != to_remove.rend(); ++it)
        {
            auto removed = *it;
            cout << "REMOVED IDX: " << distance(&*begin(s), removed) << endl; 
            result += string(start, removed);
            start = next(removed);
        }

        result += string(start, end(s));

        cout << "FIXED OPEN: " << result << endl; 
        return result;
    }

    vector<string> remove_closed(string_view s)
    {
        vector<const char*> to_remove;
        vector<string> result;

        cout << "TO FIX CLOSED: " << s << endl; 

        for (auto start = begin(s); start != end(s); start = find_if(start, end(s), [](auto ch){ return ch != ')'; }))
        {
            start = find(start, end(s), ')');
            cout << "TO REMOVE CLOSED: " << distance(begin(s), start) << endl; 
            if (start != end(s)) to_remove.push_back(start);
        }

        for (auto removed : to_remove)
        {
            auto str = string(begin(s), removed) + string(next(removed), end(s));
            cout << "FIXED CLOSED: " << str << endl; 
            result.push_back(std::move(str));
        }
        cout << "FIXED CLOSED: " << result.size() << endl;
        return result;
    }

    bool is_valid(const string& s) {
        stack<char> st;

        const auto is_open = [](char p) { return p == '('; };
        const auto is_letter = [](char p) { return p != '(' &&  p != ')'; };  

        for (auto ch : s) {
            if (is_letter(ch)) continue;

            else if (is_open(ch)) st.push(ch);
            else if (!st.empty() && is_open(st.top())) st.pop();
            else return false;
        }

        return st.empty();
    }

public:
    vector<string> removeInvalidParentheses(string s) {
        vector<string> result{""};
        auto open = 0; 

        //s = "n";

        auto is_open = [](auto ch) { return ch == '('; };
        auto is_closed = [](auto ch) { return ch == ')'; };
        auto is_letter = [](auto ch) { return ch != '(' && ch != ')'; };

        for (auto start = cbegin(s), finish = start; start != cend(s);) {
            //cout << "INDEX: " << distance(cbegin(s), start) << endl;

            while (finish != cend(s) && is_letter(*finish)) {

                ++finish;
            }
            if (distance(start, finish)) {
                for (auto& prefix : result) {
                    prefix += string(start, finish);
                }
                start = finish;
                continue;
            }

            while (finish != cend(s) && is_open(*finish)) {
                ++finish;
            }
            if (int count = distance(start, finish); count) {
                //cout << "open count: " << count << endl;
                vector<string> updated_result;
                for (auto& prefix : result) {
                    //cout << "open prefix: " << prefix << endl;
                    for (auto i = 0; i <= count; ++i) {
                        //cout << "open update: " << (prefix + string(i, '(')) << endl;
                        updated_result.push_back(prefix + string(i, '('));
                    }   
                }
                result = std::move(updated_result);
                start = finish;
                continue;               
            }

            while (finish != cend(s) && is_closed(*finish)) {
                ++finish;
            }
            if (int count = distance(start, finish); count) {
                //cout << "closed count: " << count << endl;
                vector<string> updated_result;
                for (auto& prefix : result) {
                    int open = count_if(cbegin(prefix), cend(prefix), [](auto ch) { return ch == '('; });
                    //cout << "open before closed count: " << open << endl;
                    //cout << "closed prefix: " << prefix << endl;
                    for (auto i = 0; i <= min(open, count); ++i) {
                        //cout << "closed update: " << (prefix + string(i, ')')) << endl;
                        updated_result.push_back(prefix + string(i, ')'));
                    }   
                }
                result = std::move(updated_result);
                start = finish;
                continue;               
            }
        }

        auto valid_end = remove_if(begin(result), end(result), [this](const auto& str) {
            return !is_valid(str);
        });

        // cout << "RESULT:" << endl;
        // for (const auto& str : vector<string>{ begin(result), valid_end }) {
        //     cout << str << endl;
        // }

        auto compare = [](const auto& lhs, const auto& rhs) {
            return lhs.size() > rhs.size() || (lhs.size() == rhs.size() && lhs < rhs);
        };
        set<string, decltype(compare)> sorted{ begin(result), valid_end, compare };
        // cout << "SORTED:" << endl;
        // for (const auto& str : sorted) {
        //     cout << str << endl;
        // }

        //sort(begin(result), valid_end, [](const auto& lhs, const auto& rhs) {
        //    return lhs.size() > rhs.size();
        //});

        auto result_end = find_if(begin(sorted), end(sorted), [size = begin(sorted)->size()](const auto& str) {
            return str.size() < size;
        });
        // cout << "FILTERED:" << endl;
        // for (const auto& str : sorted) {
        //     cout << str << endl;
        // }
        return { begin(sorted), result_end };
    }
};
211644