Problem Statement : https://leetcode.com/problems/longest-valid-parentheses/

Note: Go check down to view similar kind of problem and approach.

Approach:

• Ideal approach to this kind of problem is to check from both sides of the string.
• Here, we used a par variable that increments when points to ( and decrements when points to ).
• Check at what positions par = 0 and update the answer.

If you are not interested in the algorithm, please jump to the code.

Algorithm:

1. Declare two variables start = 0 and par = 0.
2. start for valid start position upto the valid end postion (where par = 0) gives the length of the valid substring.
3. Whenever par < 0 (i.e.,) wehe we encounter a ) without a matching ( one, update the valid start position to end+1 as no valid substring can have the current ).
4. Do repeat all the above steps iterating from back of the string.
5. The fourth step is needed because iterating from only side one side may not give the correct answer.
   Example: s = (((( ... () will give ans = 0 but we need ans = 2 as () is valid and it will only be encountered iterating from backside as of our algorithm.

Step wise iteration of algorithm from front side:
Given string s =

n = 9 , start = 0 , end = 0 , par = 0

Green - start, Blue - end and Red - length of valid substring

-> -> -> -> -> -> -> -> ->

Approach: Forward and Backward traversing

class Solution {
public:
    int longestValidParentheses(string s) {
        int ans = 0, start = 0, par = 0, n = s.size();
		// forward
        for(int end = 0; end < n; ++end) {
            if(s[end] == '(') par++;
            else par--;
            if(par < 0) {
                start = end+1;
                par = 0;
            }else if(par == 0) {
                ans = max(ans, end-start+1);
            }
        }
        int end = n-1; par = 0;
		// backward
        for(int start = n-1; start >= 0; --start) {
            if(s[start] == ')') par++;
            else par--;
            if(par < 0) {
                end = start-1;
                par = 0;
            }else if(par == 0) {
                ans = max(ans, end-start+1);
            }
        }
        return ans;
    }
};

Similar Problem: https://leetcode.com/problems/valid-parenthesis-string/

Upvote if you like.
Thank you.