An easy understanding solution in Java


  • 0
    W
    import java.util.Stack;
    import java.util.HashMap;
    
    public class Solution {
        public int longestValidParentheses(String s) {
            Stack<Integer> stack = new Stack<Integer>();
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    
            int length = s.length();
            int i;
        
            for (i = 0; i < length; i++) {
                char ch = s.charAt(i);
            
                if (ch == '(') {
                    stack.push(i);
                }
                if (ch == ')') {
                    if (stack.size() > 0)
                        map.put(stack.pop(), i);
                }
            }
        
            if (map.size() == 0) return 0;
        
            int max = 0, temp = 0;
            for (i = 0; i < length; i++) {
                if (map.containsKey(i)) {
                    int j = map.get(i);
                    temp += (j - i + 1);
                    i = j;
                } else {
                    if (temp > max) max = temp;
                    temp = 0;
                }
            }
        
            if (temp > max) max = temp;
        
            return max;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.