# Leetcode longest valid parentheses

Link here

I'll include a solution in Python and C++ and you can review one. I'm mostly interested in reviewing the C++ code which is a thing I recently started learning; those who don't know C++ can review Python code. Both solutions share similar logic, so the review will apply to either.

## Problem statement

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

Example 1:

Input: s = "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()".


Example 2:

Input: s = ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()".


Example 3:

Input: s = ""
Output: 0


Example 4:

Input: s = "(()()()"
Output: 6


Example 5:

Input: s = "((())((((())))"
Output: 8


Both solutions are Oⁿ and pass all test cases including the time limit however, they are taking time more than I expected, specially the c++ version though both share the same logic. I need to improve time as a priority.

longest_parentheses.py

def check_longest(s):
opened = []
closed = []
cum_distance = 0
max_distance = 0
for i, ss in enumerate(s):
if ss == ')':
if opened:
closed.append((opened.pop(), i))
if ss == '(':
opened.append(i)
closed = set(sum(closed, ()))
for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)
return max_distance

if __name__ == '__main__':
print(check_longest(')((()()()()'))


Stats:

Runtime: 272 ms, faster than 5.14% of Python3 online submissions for Longest Valid Parentheses.
Memory Usage: 15.5 MB, less than 6.57% of Python3 online submissions for Longest Valid Parentheses.


longest_parentheses.h

#ifndef LEETCODE_LONGEST_PARENTHESES_H
#define LEETCODE_LONGEST_PARENTHESES_H

#include <string_view>

int calculate_distance(size_t p_size, const std::vector<size_t> &closed);
int get_longest(const std::string_view &s);

#endif //LEETCODE_LONGEST_PARENTHESES_H


longest_parentheses.cpp

#include "longest_parentheses.h"
#include <vector>
#include <iostream>

int calculate_distance(size_t p_size, const std::vector<size_t> &closed) {
int cum_distance = 0;
int max_distance = 0;
for (size_t i = 0; i < p_size; ++i) {
if (std::find(closed.begin(), closed.end(), i) != closed.end()) {
cum_distance++;
} else {
cum_distance = 0;
}
max_distance = std::max(max_distance, cum_distance);
}
return max_distance;
}

int get_longest(const std::string_view &s) {
std::vector<size_t> opened, closed;
for (size_t i = 0; i < s.size(); ++i) {
auto ss = s[i];
if (ss == ')') {
if (!opened.empty()) {
closed.push_back({opened.back()});
closed.push_back(i);
opened.pop_back();
}
}
if (ss == '(') {
opened.push_back(i);
}
}
return calculate_distance(s.size(), closed);
}

int main() {
std::cout << get_longest(")()())");
}


Stats:

Runtime: 1276 ms, faster than 5.09% of C++ online submissions for Longest Valid Parentheses.
Memory Usage: 9.3 MB, less than 5.04% of C++ online submissions for Longest Valid Parentheses.


## 1 Answer

Here are some things that may help you improve your program.

# C++ version

## Use all of the required #includes

The type std::vector<size_t> is used in the definition of calculate_distance() in the header file, but #include <vector> is missing from the list of includes there. Also, std::max() is used, but #include <algorithm> is missing from the .cpp file.

## Minimize the interface

The .h file is a declaration of the interface to your software. The .cpp is the implementation of that interface. It is good design practice to minimize the interface to just that which is needed by outside programs. For that reason, I would remove the calculate_distance() function from the header.

## Make local functions static

With the smaller interface as advocated above, the calculate_distance function becomes an implementation detail used only within the .cpp file. For that reason, it should be made static so the compiler knows that it's safe to inline the function.

## Use a switch rather than a series of if statements

The code currently contains this:

for (size_t i = 0; i < s.size(); ++i) {
auto ss = s[i];
if (ss == ')') {
if (!opened.empty()) {
closed.push_back({opened.back()});
closed.push_back(i);
opened.pop_back();
}
}
if (ss == '(') {
opened.push_back(i);
}
}


It would be a little faster and a little easier to read if it were instead written like this:

for (size_t i = 0; i < s.size(); ++i) {
switch(s[i]) {
case ')':
if (!opened.empty()) {
closed.push_back({opened.back()});
closed.push_back(i);
opened.pop_back();
}
break;
case '(':
opened.push_back(i);
break;
}
}


## Be careful with signed vs. unsigned

What would it mean if calculate_distance return a negative number? It probably has no sensible interpretation, so for that reason, I'd recommend having it return an unsigned quantity versus a signed int.

## Write test functions

You have provided some test input in the description of the problem, but it would be good to write a full test script to exercise the function. For this kind of thing, I tend to like to use a test object. Here's the one I wrote for this code:

class ParenTest {
public:
ParenTest(std::string_view input, unsigned longest)
: input{input}
, longest{longest}
{}
unsigned operator()() const {
return static_cast<unsigned>(get_longest(input));
}
bool test() const {
return longest == operator()();
}
friend std::ostream& operator<<(std::ostream& out, const ParenTest& test) {
auto calculated = test();
return out << (calculated == test.longest ? "ok  " : "BAD ")
<< "\"" << test.input << "\", " << test.longest << ", got " << calculated << "\n";
}
private:
std::string_view input;
unsigned longest;
};


Now here are some test vectors and a main routine:

int main(int argc, char* argv[]) {
static const std::vector<ParenTest> tests{
{ "(()", 2 },
{ ")()())", 4 },
{ "", 0 },
{ "(()()()", 6 },
{ "((())((((())))", 8 },
{ "(())(())(()))", 12 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
{ "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
"(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
};
for (const auto &test : tests) {
std::cout << test;
}
}


To both assure correctness and also do some timing, I've used my stopwatch template. The final version of main looks like this:

#include "longest_parentheses.h"
#include "stopwatch.h"
#include <string_view>
#include <iostream>
#include <vector>

// the ParenTest class goes here

int main(int argc, char* argv[]) {
static const std::vector<ParenTest> tests{
{ "(()", 2 },
{ ")()())", 4 },
{ "", 0 },
{ "(()()()", 6 },
{ "((())((((())))", 8 },
{ "(())(())(()))", 12 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(())(()))", 12 },
{ "(())(())(()))(())(())(())(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
{ "(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))"
"(())(())(()))(())(())(()))(())(())(()))(())(())(()))(())(()((()))(())(())(()))(())(())(()))", 38 },
};
for (const auto &test : tests) {
std::cout << test;
}
if (argc != 2) {
std::cout << "Usage: " << argv[0] << " num_trials\n";
return 1;
}

auto iterations = std::stoul(argv[1]);

Stopwatch<> timer{};
bool valid{true}

for (auto i{iterations}; i; --i) {
valid &= tests.back().test();
}

auto elapsed{timer.stop()};
if (!valid) {
std::cout << "The program failed!\n";
return 2;
}

std::cout << iterations << " trials took " << elapsed << " microseconds\n"
" for an average of " << elapsed/iterations << " microseconds/trial\n";
}


## Use a better algorithm

The existing code is not so bad, but it's not as efficient as it could be. On my machine with the code shown above and with one million trials, it takes 5.66 microseconds per invocation of get_longest() on the longest test input, which is also the last of the set. We can do better. Here is an alternative routine that uses a std::vector to keep track of each of the starting ( as they occur, but also does the calculation of span length as it encounters each closing ). Here's how I did it:

unsigned get_longest(const std::string_view& in) {
struct Span {
std::size_t begin;
std::size_t end;
Span(std::size_t begin, std::size_t end)
: begin{begin}
, end{end}
{}
std::size_t len() const {
return end - begin + 1;
}
bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}
bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}
};
std::vector<std::size_t> parenmatch;
std::vector<Span> spans;
std::size_t longest{0};
for (std::size_t i{0}; i < in.size(); ++i) {
switch(in[i]) {
case '(':
parenmatch.push_back(i);
break;
case ')':
if (!parenmatch.empty()) {
Span curr_span{parenmatch.back(), i};
parenmatch.pop_back();
if (!spans.empty() && curr_span.is_strictly_enclosing(spans.back())) {
// destroy the last one
spans.pop_back();
}
if (!spans.empty() && curr_span.is_contiguous_with(spans.back())) {
// merge the contiguous spans
spans.back().end = curr_span.end;
} else {
spans.push_back(curr_span);
}
longest = std::max(longest, spans.back().len());
}
break;
default:
parenmatch.clear();
spans.clear();
}
}
return longest;
}


There is probably still room for improvement, but here's how this works. First, it keeps track of each Span of matching and nested parentheses. So () would be correspond to such a span, as would (()). The code uses is_strictly_enclosing to test for these. As an example, in (()), the inner pair is found first and would have a span of {1,2}. The outer pair is found last and has a span of {0,3}. If we examine the logic, it's now clear what this code is looking for:

bool is_strictly_enclosing(const Span& other) const {
return other.begin - begin == 1 &&
end - other.end == 1;
}


Secondly, there is the case of matching but non-nested parentheses such as ()() or (())(). Here again, we use a member function of Span:

bool is_contiguous_with(const Span& other) const {
return begin - other.end == 1;
}


Using this code, we get the following timing report:

1000000 trials took 562299 microseconds for an average of 0.562299 microseconds/trial

So this version of the code is about 10x faster. Note too, that it correctly handles malformed input such as ((*)) by reporting 0 for such a string.

# Python version

## Use elif for mutually exclusive conditions

The check for the opening ( uses if but it would make more sense to use elif here because the two cases (either ( or )) are the only ones considered. Making just this one change drops each iteration (using the same very long string as in the C++ code) from 74.167 microseconds to 72.444 microseconds.

## Don't update values that are unchanged

The code currently has this sequence:

for j in range(len(s)):
if j in closed:
cum_distance += 1
else:
cum_distance = 0
max_distance = max(max_distance, cum_distance)


A quick look at the code will verify that max_distance can only get a new value if the if statement is true, so let's move the line there. This drops the time down to 71.680 microseconds.

## Use a faster algorithm

Once again, what works in the C++ version also works in Python. Here's a Python version of the algorithm above:

def get_longest(s):
parenmatch = []
spans = []
longest = 0
for i, ss in enumerate(s):
if ss == '(':
parenmatch.append(i)
elif ss == ')':
if parenmatch:
curr_span = (parenmatch.pop(), i)
if spans and spans[-1][0] - curr_span[0] == 1 and curr_span[1] - spans[-1][1] == 1:
spans.pop()
if spans and curr_span[0] - spans[-1][1] == 1:
spans[-1] = (spans[-1][0], curr_span[1])
else:
spans.append(curr_span)
longest = max(longest, spans[-1][1] - spans[-1][0] + 1)
return longest


This time, the difference is not as dramatic, and the time for this function is 64.562 microseconds.