El desafío consiste en determinar si una cadena, compuesta exclusivamente por tres tipos de caracteres: '(', ')', y '*', es válida. Las reglas que definen la validez de dicha cadena son las siguientes:

1. Cada paréntesis de apertura '(' debe tener un paréntesis de cierre ')' correspondiente.
2. Cada paréntesis de cierre ')' debe tener un paréntesis de apertura '(' correspondiente.
3. Un paréntesis de apertura '(' debe preceder a su correspondiente paréntesis de cierre ')'.
4. El carácter '*' puede ser interpretado de tres maneras: como un único paréntesis de cierre ')', como un único parénteesis de apertura '(', o como una cadena vacía.
5. Una cadena vacía se considera válida.

Ejemplos:

Ejemplo 1:

Entrada: "()"
Salida: True

Ejemplo 2:

Entrada: "(*)"
Salida: True

Ejemplo 3:

Entrada: "(*))"
Salida: True

Aálisis y Estrategias de Solución

La validación de cadenas con paréntesis generalmente implica asegurarse de que cada paréntesis de apertura tenga su contraparte de cierre en la posición correcta. La introducción del carácter comodín '*' añade flexibilidad, ya que puede adoptar múltiples roles.

1. Enfoque con Programación Dinámica (Memoización)

Una estrategia efectiva es utilizar programación dinámica para resolver el problema para todas las subcadenas posibles. Definiremos dp[i][j] como un booleano que indica si la subcadena s[i...j] es válida. Los casos base y de transición son:

• Caso Base: Si i > j, la subcadena es vacía y, por lo tanto, válida (true). Si i == j (un solo carácter), la subcadena es válida solo si el carácter es '*'.
• Transición 1 (Emparejamiento de extremos): Si s[i] puede ser un paréntesis de apertura (es decir, '(' o '*') y s[j] puede ser un paréntesis de cierre (es decir, ')' o '*'), y la subcadena interna s[i+1...j-1] es válida, entonces s[i...j] es válida.
• Transición 2 (Partición): Si no se cumple el caso anterior, podemos intentar dividir la subcadena s[i...j] en dos partes en un punto k (s[i...k] y s[k+1...j]). Si ambas subcadenas son válidas de forma independiente, entonces s[i...j] también es válida.

Almacenamos los resutlados de dp[i][j] para evitar recálculos, utilizando memoización.

2. Enfoque Codicioso (Greedy) con Contadores

Un método más eficiente y con menor complejidad espacial implica el uso de dos contadores: minAbiertos y maxAbiertos. Estos contadores rastrean el número mínimo y máximo de paréntesis de apertura que podrían estar disponibles o ser necesarios a medida que recorremos la cadena de izquierda a derecha.

• minAbiertos: Representa el número mínimo de paréntesis de apertura sin cerrar que necesitamos para hacer válida la cadena hasta el punto actual, asumiendo que todos los '*' se usan para cerrar paréntesis (si es posible) o como vacíos.
• maxAbiertos: Representa el número máximo de paréntesis de apertura sin cerrar que podríamos tener, asumiendo que todos los '*' se usan como paréntesis de apertura.

Al recorrer la cadena:

• Si encontramos '(': Incrementamos ambos minAbiertos y maxAbiertos.
• Si encontramos ')': Decrementamos ambos minAbiertos y maxAbiertos.
• Si encontramos '*': Decrementamos minAbiertos (pues puede actuar como ')' o vacío) y se incrementa maxAbiertos (pues puede actuar como '(').

En cualquier punto, si maxAbiertos se vuelve negativo, significa que tenemos demasiados paréntesis de cierre sin ninguna forma de ser emparejados, por lo que la cadena es inválida. Además, minAbiertos nunca puede ser negativo; si se calcula como negativo, lo ajustamos a 0 (esto ocurre cuando un '*' o ')' cierra un paréntesis que ya no se considera necesario en el conteo mínimo, pero no implica un emparejamiento incorrecto aún).

Al finalizar el recorrido, la cadena es válida si minAbiertos es igual a 0, lo que significa que todos los paréntesis de apertura que eran estrictamente necesarios han sido emparejados.

Implementación

C++ (Programación Dinámica con Memoización)

class Solution {
public:
    std::vector<std::vector<int>> cacheResultados; // Almacena 0: inválido, 1: válido, -1: no calculado

    bool esSubcadenaValida(const std::string& s, int inicio, int fin) {
        if (inicio > fin) { // Subcadena vacía es válida
            return true;
        }
        if (cacheResultados[inicio][fin] != -1) { // Retorna resultado cacheados
            return cacheResultados[inicio][fin];
        }

        if (inicio == fin) { // Un solo carácter
            return cacheResultados[inicio][fin] = (s[inicio] == '*');
        }

        // Caso 1: Los caracteres en los extremos forman un par o pueden hacerlo con '*'
        bool posibleInicioAbierto = (s[inicio] == '(' || s[inicio] == '*');
        bool posibleFinCerrado = (s[fin] == ')' || s[fin] == '*');
        
        if (posibleInicioAbierto && posibleFinCerrado && esSubcadenaValida(s, inicio + 1, fin - 1)) {
            return cacheResultados[inicio][fin] = 1;
        }

        // Caso 2: Dividir la subcadena en dos partes válidas
        for (int p = inicio; p < fin; ++p) {
            if (esSubcadenaValida(s, inicio, p) && esSubcadenaValida(s, p + 1, fin)) {
                return cacheResultados[inicio][fin] = 1;
            }
        }
        
        return cacheResultados[inicio][fin] = 0; // Si ninguna de las condiciones anteriores se cumple
    }

    bool checkValidString(std::string s) {
        int n = s.length();
        if (n == 0) return true;
        cacheResultados.assign(n, std::vector<int>(n, -1)); // Inicializar con -1
        return esSubcadenaValida(s, 0, n - 1);
    }
};

Java (Enfoque Codicioso)

class Solution {
    public boolean checkValidString(String s) {
        int minParentesisAbiertosNecesarios = 0; // Mínimo de '(' que deben ser emparejados
        int maxParentesisAbiertosDisponibles = 0; // Máximo de '(' que pueden estar presentes, usando '*' como '('

        for (char c : s.toCharArray()) {
            if (c == '(') {
                minParentesisAbiertosNecesarios++;
                maxParentesisAbiertosDisponibles++;
            } else if (c == ')') {
                // Si encontramos ')', necesitamos un '(' menos, si es posible.
                // En el peor caso (min), el ')' consume un '('.
                // En el mejor caso (max), el ')' consume un '('.
                minParentesisAbiertosNecesarios--;
                maxParentesisAbiertosDisponibles--;
            } else { // Carácter es '*'
                // Si encontramos '*', puede cerrar un '('. Por lo tanto, necesitamos uno menos en el mínimo.
                // Si no hay '(', puede actuar como vacío, de ahí el Math.max(0, ...).
                minParentesisAbiertosNecesarios--; 
                
                // Si encontramos '*', puede ser un '('. Por lo tanto, aumentamos el máximo disponible.
                maxParentesisAbiertosDisponibles++;
            }

            // Si en algún momento maxParentesisAbiertosDisponibles es negativo, significa que hemos 
            // encontrado demasiados ')' que no pueden ser emparejados, incluso si todos los '*'
            // se usan como '('.
            if (maxParentesisAbiertosDisponibles < 0) {
                return false;
            }

            // minParentesisAbiertosNecesarios nunca puede ser negativo. Si se calcula como negativo,
            // significa que el '*' o ')' actuó como un 'vacio' o ')' para un '(' que ya no era 
            // "estrictamente" necesario.
            minParentesisAbiertosNecesarios = Math.max(0, minParentesisAbiertosNecesarios);
        }

        // Al final, la cadena es válida si no quedan paréntesis de apertura que sean estrictamente necesarios.
        return minParentesisAbiertosNecesarios == 0;
    }
}