Longest Valid Parentheses

Q: Existe-t-il une solution de programmation dynamique pour le problème de la plus longue séquence de parenthèses valides ?

Oui. Soit end[i] la longueur de la plus longue sous-chaîne bien formée qui se termine à l’index i ; elle vaut 0 lorsque s[i] est ( . Si s[i-1] est ( , alors end[i] = end[i-2] + 2 . Si c’est ) , examinons j = i - end[i-1] - 1 , le caractère avant la séquence qui se termine à i-1 : lorsque s[j] est ( , il encadre cette séquence, et end[i] = end[i-1] + 2 + end[j-1] , où le dernier terme relie une séquence qui la touche à gauche. La réponse est la plus grande valeur de end[i] , en temps et en mémoire O(n) .

DifficilePile Programmation dynamique

+10

On vous donne une chaîne s composée uniquement des caractères ( et ). Trouvez la plus longue sous-chaîne (une suite de caractères consécutifs) bien formée : chaque ( qu’elle contient est fermé par un ) qui apparaît plus loin dans cette sous-chaîne, et les paires sont correctement imbriquées, comme dans (()()). Renvoyez la longueur de cette sous-chaîne, ou 0 si même () n’apparaît pas.

Fonction

longestValidParentheses(s: string) → integer

sstring: une chaîne de caractères composée de ( et de )
Renvoieinteger: la longueur de la plus longue sous-chaîne bien formée, ou 0 s’il n’y en a aucune

Contraintes

1 ≤ s.length ≤ 6 × 10⁴
Chaque caractère de s est ( ou ).

Exemples

Entrée: s = "()(())"
Sortie: 6
Explication: La chaîne entière est bien formée : () suivi de (()). Deux éléments bien formés côte à côte forment un seul élément bien formé, donc la réponse est constituée des 6 caractères.

Entrée: s = "())((())"
Sortie: 4
Explication: Le ) à l’index 2 n’a pas de partenaire, donc aucune réponse ne peut le traverser, et le ( à l’index 3 n’est jamais fermé. Le plus long segment est (()) de l’index 4 à 7, d’une longueur de 4, ce qui est plus long que le () au début.

Entrée: s = "))(("
Sortie: 0
Explication: Les deux ) apparaissent avant les deux (, donc aucun ( n’est jamais fermé. Aucune sous-chaîne n’est bien formée et la réponse est 0.

+21 tests cachés à la soumission

Pour aller plus loin

Peux-tu également indiquer où commence la plus longue sous-chaîne bien formée, en choisissant celle qui apparaît le plus à gauche lorsque plusieurs ont la même longueur ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Deux éléments rendent cela plus difficile que la vérification d’une seule chaîne. Les morceaux bien formés se rejoignent lorsqu’ils se touchent, donc () et (()) côte à côte comptent comme une seule séquence de 6. Et un caractère isolé, tel que le ) dans ())(()), coupe la chaîne : aucune solution ne peut le traverser. Tester chaque position de départ coûte O(n²). La solution consiste à mémoriser le début de la séquence en cours : une pile d’indices avec un marqueur de base au fond permet de le faire en un seul parcours, et deux parcours avec de simples compteurs le permettent sans pile.

Développer une sous-chaîne à partir de chaque position de départ

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Parcourez une sous-chaîne de gauche à droite en maintenant un solde qui augmente de 1 pour ( et diminue de 1 pour ). La sous-chaîne est bien formée exactement lorsque le solde ne passe jamais en dessous de 0 et se termine à 0. Un solde inférieur à 0 signifie qu’un ) est arrivé sans rien d’ouvert à fermer.

Fixez donc un début et avancez vers la droite, en mettant à jour le solde caractère par caractère. Chaque fois qu’il revient à 0, la portion du début jusqu’ici est bien formée, et vous en notez la longueur. Dès qu’il passe en dessous de 0, arrêtez-vous : ce ) reste sans correspondance dans toutes les portions plus longues à partir de ce début. Chaque sous-chaîne bien formée a un début, et vous essayez toutes ses fins, donc rien n’est oublié.

Le problème, c’est le coût. Dans une chaîne composée de 59998 ( suivis de (), le solde ne passe jamais en dessous de 0, donc chaque début est parcouru jusqu’à la fin : environ n²/2 = 1.8 × 10^9 étapes pour n = 6 × 10^4. Les grands tests sont construits ainsi. (Vérifier chaque sous-chaîne depuis le début au lieu de la développer serait encore pire, O(n³).)

Algorithme

Définis best à 0.
Pour chaque début, définis balance à 0 et parcours la fin depuis le début jusqu’au dernier caractère.
Ajoute 1 pour ( et soustrais 1 pour ).
Si balance est inférieur à 0, arrête ce parcours. S’il vaut 0, mets à jour best avec la longueur de la séquence end - start + 1.
Retourne best.

def longestValidParentheses(s):
    best = 0
    for start in range(len(s)):
        balance = 0
        for end in range(start, len(s)):
            balance += 1 if s[end] == "(" else -1
            if balance < 0:
                # A ')' without a partner: no longer run starts here
                break
            if balance == 0:
                best = max(best, end - start + 1)
    return best

Pile d’indices avec un marqueur de base

Intuition

Associer des parenthèses à l’aide d’une pile est familier : empilez chaque (, dépilez-en une pour chaque ). Ici, vous avez aussi besoin des longueurs : empilez donc des indices et gardez un indice supplémentaire au bas de la pile : la base, la position juste avant la séquence en cours. Au début, rien n’a été lu, donc la base est -1.

Pour (, empilez son indice. Pour ), dépilez. Deux choses peuvent se produire. Si la pile est maintenant vide, vous avez dépilé la base : ce ) n’avait rien à fermer. Aucune sous-chaîne bien formée ne peut le contenir, et il devient la nouvelle base : empilez son indice. Sinon, l’indice resté au sommet est le dernier caractère avant la séquence qui se termine à i : soit un ( encore ouvert, soit la base. Tout ce qui se trouve après lui jusqu’à i est apparié, et la séquence ne peut pas remonter plus à gauche, donc sa longueur est i - top.

Voici ())((()) :

i = 0, ( : empilez 0. Pile [-1, 0].
i = 1, ) : dépilez 0. Le sommet est -1, donc la séquence mesure 1 - (-1) = 2.
i = 2, ) : dépilez -1 et la pile est vide. Ce ) n’a pas de partenaire, alors empilez 2 comme nouvelle base. Pile [2].
i = 3, 4, 5, trois ( : empilez-les. Pile [2, 3, 4, 5].
i = 6, ) : dépilez 5. Le sommet est 4, donc la séquence mesure 6 - 4 = 2.
i = 7, ) : dépilez 4. Le sommet est 3, donc la séquence mesure 7 - 3 = 4, la réponse.

La base permet de joindre les segments adjacents. Pour ()(()), la première paire mesure 1 - (-1) = 2, et le dernier ) dépile l’indice 2 et trouve à nouveau -1 au sommet, donc il mesure 5 - (-1) = 6. Mesurer à partir du ( correspondant donnerait plutôt 4 et ne tiendrait pas compte du () qui le précède. Chaque indice est empilé et dépilé au plus une fois, donc le parcours est en O(n), et la pile peut contenir jusqu’à n+1 indices.

Algorithme

Commence une pile contenant -1 et définis best à 0.
Pour chaque index i, empile i si s[i] est (.
S’il s’agit de ), dépile une fois.
Si la pile est maintenant vide, empile i comme nouvelle base. Sinon, mets à jour best avec i - top.
Retourne best.

def longestValidParentheses(s):
    # The bottom of the stack is the index just before the current run
    stack = [-1]
    best = 0
    for i, ch in enumerate(s):
        if ch == "(":
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                # This ')' has no partner: it becomes the new base
                stack.append(i)
            else:
                best = max(best, i - stack[-1])
    return best

Compter les ouvertures et les fermetures en deux passes

Intuition

La pile t’indique uniquement où la séquence valide en cours a commencé. Deux compteurs peuvent faire la même chose. Parcours la chaîne de gauche à droite en comptant les opens et les closes depuis la dernière réinitialisation. Quand ils sont égaux, tout ce qui se trouve depuis la réinitialisation est bien formé, et sa longueur est 2 × closes. Quand closes prend le dessus, une ) n’a pas de partenaire, au même moment où la pile a perdu sa base : réinitialise alors les deux compteurs à 0.

Un seul parcours ne suffit pas. Une ( qui ne se ferme jamais maintient opens en tête définitivement, et les compteurs ne seront plus jamais égaux. Avec ((), le parcours de gauche se termine avec 2 ouvertures et 1 fermeture et ne trouve rien, alors que () est juste là. Il faut donc parcourir la chaîne une seconde fois, de droite à gauche, en inversant les rôles : réinitialise quand opens prend le dessus. En lisant à l’envers, (() donne une fermeture, puis une ouverture (égalité : longueur 2), puis une ouverture qui entraîne une réinitialisation. La réponse est le maximum des résultats des deux parcours.

Pourquoi deux parcours permettent de trouver toutes les séquences : la plus longue séquence est délimitée par des caractères qui ne peuvent jamais être appariés, ou par les extrémités de la chaîne. Si sa limite gauche est une ) isolée ou le début de la chaîne, le parcours de gauche réinitialise les compteurs juste là où la séquence commence et constate leur égalité là où elle se termine. Si sa limite gauche est une ( isolée, sa limite droite ne peut pas être une ), car cette ) fermerait la ( isolée et la séquence serait plus longue. La limite droite est donc une ( isolée ou la fin de la chaîne, et le parcours de droite trouve la séquence de la même manière. Chaque parcours lit la chaîne une fois avec deux entiers : le temps d’exécution est donc O(n) et la mémoire supplémentaire est de O(1).

Algorithme

Définis best à 0, et opens et closes à 0.
Parcours de gauche à droite en comptant chaque caractère. Lorsque les compteurs sont égaux, mets à jour best avec 2 × closes. Lorsque closes est supérieur, remets les deux compteurs à 0.
Réinitialise les deux compteurs, puis parcours de droite à gauche de la même manière, sauf que tu les réinitialises lorsque opens est supérieur.
Renvoie best.

def longestValidParentheses(s):
    best = 0

    # Left to right: more ')' than '(' ends every run that started earlier
    opens = closes = 0
    for ch in s:
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * closes)
        elif closes > opens:
            opens = closes = 0

    # Right to left: catches the runs that an unmatched '(' hid from the first pass
    opens = closes = 0
    for ch in reversed(s):
        if ch == "(":
            opens += 1
        else:
            closes += 1
        if opens == closes:
            best = max(best, 2 * opens)
        elif opens > closes:
            opens = closes = 0

    return best

Pièges et cas limites

La plupart des mauvaises réponses comptent les bonnes paires aux mauvais endroits ou perdent le début d’une séquence.

Compter les paires correspondantes dans toute la chaîne. ())((()) contient 3 paires, mais elles ne se suivent pas toutes, et la réponse est 4, pas 6.
Mesurer une séquence à partir de la parenthèse correspondante (. Dans ()(()), le dernier ) correspond à l’indice 2, ce qui donne 4 et ne tient pas compte de () au début. Mesure à partir de l’indice restant sur la pile après le dépilement.
Commencer avec une pile vide. Le premier ) de ()) n’a alors rien à quoi se comparer, et un ) sans correspondance dépile une pile vide. La base -1 corrige ces deux problèmes.
Exécuter les compteurs dans une seule direction. (() renvoie 0 de gauche à droite, et ()) renvoie 0 de droite à gauche ; la réponse est 2 dans les deux cas.
Réinitialiser les compteurs lorsqu’ils sont égaux. Des nombres égaux signifient que la séquence peut encore s’allonger, comme dans ()() ; réinitialise uniquement lorsqu’un côté prend l’avantage.
En Lua et en R, les positions commencent à 1 : la première base est donc 0, et non -1.

Questions fréquentes4

Quelle est la complexité temporelle du problème de la plus longue séquence de parenthèses valides ?

La solution avec pile et la solution avec compteurs en deux passes lisent chaque caractère un nombre constant de fois, elles s’exécutent donc en temps O(n). Dans le pire des cas, la pile nécessite une mémoire de O(n), par exemple avec une chaîne composée uniquement de (, tandis que les compteurs nécessitent O(1). Essayer chaque position de départ prend O(n²).

Pourquoi la pile commence-t-elle à -1 ?

La longueur de la séquence est l’index actuel moins l’index juste avant la séquence. Pour une séquence qui commence à l’index 0, cet index précédent est -1, soit une position avant la chaîne. Empiler -1 en premier signifie que la pile n’est jamais vide lorsqu’une ) correspondante mesure la longueur, et lorsqu’une ) sans correspondance la dépile, cette ) devient la nouvelle base.

Existe-t-il une solution de programmation dynamique pour le problème de la plus longue séquence de parenthèses valides ?

Oui. Soit end[i] la longueur de la plus longue sous-chaîne bien formée qui se termine à l’index i ; elle vaut 0 lorsque s[i] est (. Si s[i-1] est (, alors end[i] = end[i-2] + 2. Si c’est ), examinons j = i - end[i-1] - 1, le caractère avant la séquence qui se termine à i-1 : lorsque s[j] est (, il encadre cette séquence, et end[i] = end[i-1] + 2 + end[j-1], où le dernier terme relie une séquence qui la touche à gauche. La réponse est la plus grande valeur de end[i], en temps et en mémoire O(n).

Pourquoi un seul passage avec des compteurs ne suffit-il pas ?

Un parcours de gauche à droite ne se réinitialise que lorsque le nombre de ) dépasse celui des (. Une ( supplémentaire qui n’est jamais fermée maintient les nombres différents pour le reste de la chaîne, si bien que le parcours ne les voit jamais se rejoindre. Dans ((), il se termine avec 2 parenthèses ouvrantes et 1 parenthèse fermante, et ne trouve rien. Lire de droite à gauche traite la ( isolée comme le premier parcours traite une ) isolée, ainsi les deux parcours couvrent ensemble toutes les séquences.

Python

def longestValidParentheses(s):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "()(())"

Attendu

Longest Valid Parentheses

Fonction

Contraintes

Exemples

Indices

Solution

Développer une sous-chaîne à partir de chaque position de départ

Pile d’indices avec un marqueur de base

Compter les ouvertures et les fermetures en deux passes

Pièges et cas limites

Questions fréquentes4

Problèmes similaires