public int longestValidParentheses_3(String s) { // solution where indices are stored in the stack
		if(s == null || s.length() == 0) return 0;
		Stack<Integer> stk = new Stack<Integer>();
		int res = 0;
		for(int i = 0; i < s.length(); ++i){
			char c = s.charAt(i);
			if(c == '(') stk.push(i);
			else if(c == ')'){
				if(!stk.isEmpty() && s.charAt(stk.peek()) == '(') {
					stk.pop();
					res = Math.max(res, stk.isEmpty()?i+1:i - stk.pop());
				}
				else stk.push(i);
			}
		}
        return res;
    }