## (Longest Palindromic Substring)

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.
For “(()”, the longest valid parentheses substring is “()”, which has length = 2.
Another example is “)()())”, where the longest valid parentheses substring is “()()”, which has length = 4.

Thoughts:
The idea is to use a stack to store all the index of ‘(‘ we encountered. We maintain a variable “startIndex” to store the earliest starting position of a ‘(‘, this is used to determine the start position (hence the length) of a possible solution. If we see a ‘)’, we can pop out a ‘(‘ to construct a parenthesis. Hence we have a candidate. After doing that, if the stack is empty, we can fetch the earliest starting position to calculate the length of this solution (this scenario occurs when we see the last index of “(()())”). If the stack is not empty yet, we can calculate the length by comparing the current index with the index of the top element in the stack (this scenario happens when we process the last index of “(()”).
Code (Java):

```import java.util.Stack;
public class Solution {
public int longestValidParentheses(String s) {
Stack<Integer> stack = new Stack<Integer>();
int len = 0;
int maxLen = 0;
int startIndex = s.length();
for(int i = 0; i < s.length(); ++i) {
if(s.charAt(i) == '(') {
stack.push(i);
continue;
}

if(stack.isEmpty()) {
startIndex = s.length();
} else {
startIndex = Math.min(stack.peek(), startIndex);
stack.pop();

if(stack.isEmpty()) {
len = i - startIndex + 1;
} else {
len = i - stack.peek();
}
maxLen = Math.max(maxLen, len);
}
}
return maxLen;
}
}

Code (C++):
class Solution {
public:
int longestValidParentheses(string s) {
stack<int> Stack;
int len = 0;
int maxLen = 0;
int startIndex = s.size();
for(int i = 0; i < s.size(); ++i) {
if(s[i] == '(') {
Stack.push(i);
continue;
}

if(Stack.empty()) {
startIndex = s.size();
} else {
startIndex = min(Stack.top(), startIndex);
Stack.pop();

if(Stack.empty()) {
len = i - startIndex + 1;
} else {
len = i - Stack.top();
}
maxLen = max(maxLen, len);
}
}
return maxLen;
}
};

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5bcfbdcebdf8d', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5bcfbdcebdfb6',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5bcfbdcebdfb8',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});