LeetCode problem #32 — Longest Valid Parentheses (JavaScript)

In this LeetCode problem, we’re supplied with a string of parentheses (( and )), and asked to find the length of the longest valid sub-string of parentheses. Valid is defined as a correctly open and closed set of parentheses, such as (), (()), ()(), etc.

Solution #1: Finding all valid possibilities

This is notionally known as the brute force method, and is most definitely the slowest valid option. In this approach, we loop through the supplied string, and create a “potentially valid string” (PVS) every time we encounter an open-parentheses. We then continue traversing the string until said PVS is correctly closed, at which point we consider the PVS as valid, and return the longest one found.

Whilst the easiest to explain, this is unfortunately the most inefficient, as we are not only storing more data, but carrying out far more calculations, than the next approach.

Solution #2: Identifying the incorrect characters

This approach (which is inspired by a number of posters, but predominantly floribon with his submission) does the opposite of the above, by instead looking for all of the invalid parentheses. Once we know all of the invalid parentheses, we can then assume that the strings between said invalid parentheses are valid, and thus calculate the biggest of those.

Computationally this approach is far better, but it’s definitely more difficult to wrap your head around, and relies on an assumption that does not seem entirely intuitive (but is evidently correctly, at least in the test cases supplied by LeetCode).