LeetCode – Paréntesis válidos más largos (Java)

Dada una cadena que contenga solo los caracteres ‘(‘ y ‘)’, encuentre la longitud de la subcadena de paréntesis válida más larga (bien formada).

Para «(()», la subcadena de paréntesis válida más larga es «()», que tiene una longitud = 2.
Otro ejemplo es «) () ())», donde la subcadena de paréntesis válida más larga es «() ()», que tiene una longitud = 4.

Solución Java

Se puede usar una pila para rastrear y reducir pares. Dado que el problema pide la longitud, podemos poner el índice en la pila junto con el carácter. Para simplificar la codificación, podemos usar 0 para representar (y 1 para representar).

Este problema es similar con los paréntesis válidos, que también se pueden resolver utilizando una pila.

public int longestValidParentheses(String s) {
    Stack<int[]> stack = new Stack<>();
    int result = 0;
 
    for(int i=0; i<s.length(); i++){
        char c = s.charAt(i);
        if(c==')'){
            if(!stack.isEmpty() && stack.peek()[0]==0){
                stack.pop();
                result = Math.max(result, i-(stack.isEmpty()?-1:stack.peek()[1]));
            }else{
                stack.push(new int[]{1, i});
            }
        }else{
            stack.push(new int[]{0, i});
        }
    }
 
    return result;
}