32 Longest Valid Parentheses

Given a string containing just the characters'('and')', find the length of the longest valid (well-formed) parentheses substring.

For"(()", the longest valid parentheses substring is"()", which has length = 2.

Another example is")()())", where the longest valid parentheses substring is"()()", which has length = 4.

The Idea: First I create a vector that that iterates through the original string s and counts the relative number of matching parenthesis. For example:

Ex. 1

0 1 2 3 4 5
x 1 0 1 0 x
) ( ) ( ) )


Ex. 2

0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2
x 1 2 3 4 5 6 5 6 5 4 5 4 5 4 3 2 3 2 3 4 3 2
) ( ( ( ( ( ( ) ( ) ) ( ) ( ) ) ) ( ) ( ( ) )


Ex. 3

0 1 2 3 4 5 6 7 8 9 0
1 2 1 0 1 0 1 2 1 2 3
( ( ) ) ( ) ( ( ) ( (

Parentheses that are known to be impossibly matched are set to -1 (shown as x). This is identified when the current number of ')' exceeds '('. Using this array, a properly matched paranthesis could then be identified in the array as a n to the first n-1 pair. Starting from the beginning of the string and iterating towards the right, we are able to identify the longest n to n-1 pair. However, it may follow that there another set of valid paranthesis right after the previous matching pair, and if so - this too must be included in the maximum length. So to do this, I simply go through the operation of finding all the longest n to n-1 pairs that follow one another. In the end I get something along the lines of:

+---------+       +--+   ++ +-------+--------+---+-+

This gives us a set of non overlapping intervals to work with. I then merge continuous intervals (intervals where the the i+1th interval end connects with ith interval start). Finally, I iterate through these interval to return the largest width.

Complexity: O(n^2) time O(n) space. The worst case can be identified with the string s = "((((((((((((((((..." since get_first_valid_match tries to anticipate a match with proceeding (.

Attempt 1

//STATUS: time limit exceeded

vector<int> match_paren(const string &s) {
    vector<int> matches; matches.reserve(s.size());
    int l_r_balance = 0;

    for (const char c : s) {
        if (c == '(') l_r_balance++;
        else if (c == ')') l_r_balance--;
        if (l_r_balance < 0) {
            matches.push_back(-1);
            l_r_balance++;
        }
        else {
            matches.push_back(l_r_balance);
        }
    }

    return matches;
}


template<typename T>
pair<T,T> get_first_valid_match(T begin, T end) {
    for (auto i = begin; i != end; ++i) {
        for (auto j = i + 1; j != end; ++j) {
            if (*j == *i - 1 && *i >= 0 && *j >= 0) {
                return {i, j};
            }
        }
    }
    return { end, end };
}

using v_iter = vector<int>::iterator;
vector<pair<v_iter, v_iter>> merge_intervals(const vector<pair<v_iter, v_iter>> &intervals) {
    vector<pair<v_iter, v_iter>> merged;
    if (intervals.empty()) return merged;

    merged.push_back(intervals[0]);
    for (int i = 0; i < intervals.size(); i++) {
        for (int j = i + 1; j < intervals.size(); j++) {

            if (merged.back().second == intervals[j].first - 1) {
                merged.back().second = intervals[j].second;
            }
            else {
                merged.push_back(intervals[j]);
                i = j - 1;
                break;
            }

        }
    }
    return merged;
}

int find_max_interval(const vector<pair<v_iter, v_iter>> &merged) {
    int max_d = 0;
    for (auto &pair : merged) {
        int dist = distance(pair.first, pair.second) + 1;
        max_d = max(max_d, dist);
    }
    return max_d;
}

int longestValidParentheses(string s) {
    vector<int> matches = match_paren(s);

    vector<pair<v_iter, v_iter>> valid_intervals;
    v_iter left_off = matches.begin();

    while (left_off != matches.end()) {
        pair<v_iter, v_iter> next_interval = get_first_valid_match(left_off, matches.end());

        if (next_interval.first == matches.end() && next_interval.second == matches.end())
            break;

        valid_intervals.push_back(next_interval);
        left_off = next_interval.second;
        if (left_off != matches.end()) left_off++;
    }

    vector<pair<v_iter, v_iter>> merged = merge_intervals(valid_intervals);
    return find_max_interval(merged);
}

Testing

int main()
{
    string t1 = "(()"; // 2
    string t2 = ")()())"; // 4
    string t3 = "()()()()()())))))(((())))"; // 12
    string t4 = "()()()())))((()))"; // 8
    string t5 = "()()()))((()()))"; // 8
    string t6 = "()())(()))()"; // 4
    string t7 = "()(()"; // 2
    string t8 = ")(((((()())()()))()(()))("; // 22
    string t9 = ")(())))(())())"; // 6
    string t10 = "((((((((((((((("; // 0

    assert(longestValidParentheses(t1) == 2);
    assert(longestValidParentheses(t2) == 4);
    assert(longestValidParentheses(t3) == 12);
    assert(longestValidParentheses(t4) == 8);
    assert(longestValidParentheses(t5) == 8);
    assert(longestValidParentheses(t6) == 4);
    assert(longestValidParentheses(t7) == 2);
    assert(longestValidParentheses(t8) == 22);
    assert(longestValidParentheses(t9) == 6);
    assert(longestValidParentheses(t10) == 0);
}

Attempt 2

The Idea: The approach this time around is very similar with the previous. The main difference is that now to collect the valid intervals a stack is used. A valid interval is found the moment s[i] = ')' and the stack is not empty. After collecting these intervals, we sort by their start time. This ensures that when we merge the intervals next, continuous intervals will be lined up nicely for the merge.

)(())))(())())
 (  )
  () 
       (  )        
        ()
           ()

Overlapping intervals can get ignored with a simple check (their end time is within the range of the previous end time).

Complexity: O(N + NlogN + N + N) for stack ops, sorting, merging, and find max, respectfully. O(N)space.

vector<pair<int, int>> merge_intervals(vector<pair<int, int>> &intervals) {
    vector<pair<int, int>> merged;
    if (intervals.empty()) return merged;
    sort(intervals.begin(), intervals.end(), [](pair<int, int> &left, pair<int, int> &right) {
        return left.first < right.first;
    });

    merged.push_back(intervals[0]);
    for (int i = 0; i < intervals.size(); i++) {
        for (int j = i + 1; j < intervals.size(); j++) {
            if (merged.back().second == intervals[j].first - 1) {
                merged.back().second = intervals[j].second;
            }
            // ignore overlapping intervals
            else if (intervals[j].second > merged.back().second){
                merged.push_back(intervals[j]);
                i = j - 1;
                break;
            }
        }
    }
    return merged;
}

int longestInterval(const vector<pair<int, int>> &intervals) {
    int max_d = 0;
    for (auto & p : intervals)
        max_d = max(max_d, p.second - p.first + 1);

    return max_d;
}

int longestValidParentheses(string s) {
    vector<pair<int,int>> valid;
    stack<int> stack;

    for (int i = 0; i < s.length(); i++) {
        if (s[i] == '(') stack.push(i);
        else if (s[i] == ')' && !stack.empty()) {
            valid.push_back({ stack.top(), i });
            stack.pop();
        }
    }

    return longestInterval(merge_intervals(valid));
}