Analyse du Problème de Parenthèses Valides

Ce défi algorithmique consiste à analyser une chaîne de caractères composée exclusivement de parenthèses ouvrantes ( et fermantes ). L'objectif est d'identifier la longueur maximale d'une sous-chaîne continue qui respecte la syntaxe correcte des parenthèses.

Visualisation de la Logique

Pour comprendre la structure des données nécessaires, observons comment les indices sont traités lors du parcours.

Approche par Tableau (Programmation Dynamique)

Chaîne : ( ) ) ( ( ) )
Indices: 0 1 2 3 4 5 6
État DP: 0 2 0 0 0 2 4

Détails :
- Index 0 : '(' seul, valeur 0
- Index 1 : '()' complet, valeur 2
- Index 2 : ')' isolé, valeur 0
- Index 5 : '()' local, valeur 2
- Index 6 : Combinaison avec précédent, valeur 4

Approche par Pile

Flux : ( ) ) ( ( ) )
Pile : [-1]           (Base)
       [-1, 0]        (Push 0)
       [-1]           (Pop, Calc: 1 - (-1) = 2)
       [2]            (Reset base to 2)
       [2, 3]         (Push 3)
       [2, 3, 4]      (Push 4)
       [2, 3]         (Pop, Calc: 5 - 3 = 2)
       [2]            (Pop, Calc: 6 - 2 = 4)

Méthodes de Résolution

1. Programmation Dynamique

Cette technique repose sur la construction d'un tableau où chaque cellule tableau[i] stocke la longueur de la séquence valide se terminant exactement à l'index i.

La logique de transition d'état se divise en deux cas principaux lorsque le caractère courant est une parenthèse fermante :

• Si le caractère précédent est une ouvrante (, nous formons une paire simple ().
• Si le caractère précédent est une fermante ), nous devons vérifier plus loin dans la chaîne pour trouver l'ouvrante correspondante.

La complexité temporelle est linéaire O(n) tout comme la complexité spatiale.

2. Utilisation d'une Pile

Une pile permet de suivre les indices des parenthèses non appariées. En initialisant la pile avec une valeur de base (généralement -1), nous pouvons calculer la longueur actuelle en soustrayant l'indice au sommet de la pile de l'indice courant lors d'une correspondance.

Cette méthode offre également une complexité O(n) en temps et en espace.

3. Balayage Double Sens

Cette optimisation permet de réduire l'espace mémoire à O(1). Elle imlpique deux passages sur la chaîne :

1. Un parcours de gauche à droite pour compter les ouvrantes et fermantes.
2. Un parcours de droite à gauche pour capturer les cas où les ouvrantes dominent au début.

Les compteurs sont réinitialisés dès qu'un déséquilibre invalide la séquence en cours.

Implémentation en C#

Soluttion par Programmation Dynamique

public class Solution {
    public int LongestValidParentheses(string s) {
        if (string.IsNullOrWhiteSpace(s)) return 0;
        
        int longueurMax = 0;
        int[] historique = new int[s.Length];
        
        for (int i = 1; i < s.Length; i++) {
            if (s[i] == ')') {
                if (s[i - 1] == '(') {
                    historique[i] = 2 + (i >= 2 ? historique[i - 2] : 0);
                } 
                else if (i - historique[i - 1] > 0) {
                    int indexMatch = i - historique[i - 1] - 1;
                    if (indexMatch >= 0 && s[indexMatch] == '(') {
                        historique[i] = historique[i - 1] + 2;
                        if (indexMatch > 0) {
                            historique[i] += historique[indexMatch - 1];
                        }
                    }
                }
                longueurMax = Math.Max(longueurMax, historique[i]);
            }
        }
        
        return longueurMax;
    }
}

Solution par Pile

public class Solution {
    public int LongestValidParentheses(string s) {
        int resultatMax = 0;
        Stack<int> pileIndices = new Stack<int>();
        pileIndices.Push(-1);
        
        for (int courant = 0; courant < s.Length; courant++) {
            if (s[courant] == '(') {
                pileIndices.Push(courant);
            } else {
                pileIndices.Pop();
                if (pileIndices.Count == 0) {
                    pileIndices.Push(courant);
                } else {
                    int longueurActuelle = courant - pileIndices.Peek();
                    resultatMax = Math.Max(resultatMax, longueurActuelle);
                }
            }
        }
        
        return resultatMax;
    }
}

Solution par Balayage Double

public class Solution {
    public int LongestValidParentheses(string s) {
        int meilleurScore = 0;
        int ouvantes = 0, fermantes = 0;
        
        // Passage gauche vers droite
        for (int i = 0; i < s.Length; i++) {
            if (s[i] == '(') ouvantes++;
            else fermantes++;
            
            if (ouvantes == fermantes) {
                meilleurScore = Math.Max(meilleurScore, 2 * fermantes);
            } else if (fermantes > ouvantes) {
                ouvantes = 0;
                fermantes = 0;
            }
        }
        
        // Passage droite vers gauche
        ouvantes = 0;
        fermantes = 0;
        for (int i = s.Length - 1; i >= 0; i--) {
            if (s[i] == '(') ouvantes++;
            else fermantes++;
            
            if (ouvantes == fermantes) {
                meilleurScore = Math.Max(meilleurScore, 2 * ouvantes);
            } else if (ouvantes > fermantes) {
                ouvantes = 0;
                fermantes = 0;
            }
        }
        
        return meilleurScore;
    }
}

Comparaison des Approches

Gestion des Cas Limites

Lors de l'implémentation, plusieurs pièges courants doivent être évités :

• Vérifier systématiquement si la chaîne est vide ou nulle avant itération.
• Dans la méthode dynamique, s'assurer que les accès aux indices i-2 ou i-dp[i-1]-2 ne provoquent pas d'erreur de bounds.
• Pour la pile, l'initialisation avec -1 est cruciale pour calculer correctement la longueur dès le premier caractère valide.
• Dans le balayage double, la condition de réinitialisation des compteurs doit être stricte pour ne pas compter des séquences invalides.