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.
