Sure! If you find a valid parentheses substring in S, you cannot possibly find another one that starts inside, but ends outside, the first one. In order for that to be the case, you'd have to have an unmatched parenthesis in the first substring, which would make that substring not valid, by definition.
That makes a big difference, because it means we don't need to check every index as a starting point for a valid parentheses substring, which would be O(N^2) time. We can instead use a greedy approach in O(N) time.
Since valid substrings can fully contain other valid substrings, however, we need the help of a stack.
For further actions, you may consider blocking this person and/or reporting abuse
We're a place where coders share, stay up-to-date and grow their careers.
Can you elaborate what do you mean by this " you can't have two substrings that only partially overlap." ? Appreciate your help :)
Sure! If you find a valid parentheses substring in S, you cannot possibly find another one that starts inside, but ends outside, the first one. In order for that to be the case, you'd have to have an unmatched parenthesis in the first substring, which would make that substring not valid, by definition.
That makes a big difference, because it means we don't need to check every index as a starting point for a valid parentheses substring, which would be O(N^2) time. We can instead use a greedy approach in O(N) time.
Since valid substrings can fully contain other valid substrings, however, we need the help of a stack.