[C++] Easy to Understand
Rather than working with complex valid parenthesis strings, we just mark all of the occurences where an open parenthesis matches a close parenthesis. The idea i
Rather than working with complex valid parenthesis strings, we just mark all of the occurences where an open parenthesis matches a close parenthesis. The idea is to then concatenate all of these individual valid parentheses to identify the longest valid streak of parentheses.\n\nFirst, we iterate through the string, keeping track of the indices of open parentheses in a stack. Every time we hit a close parenthesis, we know that the last open and the current close are both valid, so we mark both of these as being valid by overwriting them in the original string with `*`.\n\nOnce we have all of the valid individual parentheses marked, we iterate through the string once more and identify the longest sequence of `*`, which is our answer.\n```cpp\nint longestValidParentheses(string s) {\n\tstack<int> opens;\n\tfor(int i = 0; i < s.size(); i++) {\n\t\tif(s[i] == \'(\') opens.push(i);\n\t\telse if(opens.size()) {\n\t\t\ts[opens.top()] = s[i] = \'*\';\n\t\t\topens.pop();\n\t\t}\n\t}\n\n\tint curr = 0, res = 0;\n\tfor(int i = 0; i <= s.size(); i++) {\n\t\tif(s[i] == \'*\') curr++;\n\t\telse {\n\t\t\tres = max(res, curr);\n\t\t\tcurr = 0;\n\t\t}\n\t}\n\n\treturn max(curr, res);\n}\n```\n\n---\n\n**Alternate Solution:**\n\nTo reduce memory usage, we can take another approach. Scan the string from left to right, replacing any invalid parentheses with `*`. Then repeat the process, scanning from right to left. The string we\'re left with should have "pockets" of valid parentheses strings separated by `*`. We simply have to iterate through the string and count the longest stretch of parentheses.\n```\nint longestValidParentheses(string s, int res = 0) {\n\tfor (int i = 0, n = 0; i < s.size(); ++i)\n\t\tif (s[i] == \'(\') ++n;\n\t\telse if (!n--) s[i] = \'*\', n = 0;\n\tfor (int i = s.size() - 1, n = 0; i >= 0; --i) \n\t\tif (s[i] == \')\') ++n;\n\t\telse if (s[i] == \'*\') n = 0;\n\t\telse if (!n--) s[i] = \'*\', n = 0;\n\tfor (int i = 0, cur = 0; i < s.size(); ++i)\n\t\tif (s[i] != \'*\') res = max(res, ++cur);\n\t\telse cur = 0;\n\treturn res;\n}\n```
['C', 'C++']