(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;
    }
};
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: