Longest Palindromic Substring

MoyenDeux pointeurs Programmation dynamique

+10

Vous recevez une chaîne s composée de lettres minuscules de l’alphabet anglais. Renvoyez sa plus longue sous-chaîne palindromique : la plus longue suite de lettres consécutives qui se lit de la même façon de gauche à droite et de droite à gauche. Si plusieurs sous-chaînes ont cette longueur maximale, renvoyez celle qui commence le plus à gauche.

Fonction

longestPalindrome(s: string) → string

sstring: la chaîne en minuscules à rechercher
Renvoiestring: la plus longue sous-chaîne palindromique de s, la plus à gauche en cas d’égalité

Contraintes

1 ≤ s.length ≤ 2000
s contient uniquement des lettres minuscules anglaises.
Lorsque plusieurs palindromes ont la longueur maximale, la réponse est celui dont l’indice de début est le plus petit.

Exemples

Entrée: s = "bananas"
Sortie: "anana"
Explication: "anana" se lit de la même façon des deux côtés et comporte 5 lettres. Aucun morceau plus long ne fonctionne : "banana" commence par b et se termine par a, "ananas" commence par a et se termine par s, et le mot entier commence par b et se termine par s.

Entrée: s = "xyzzyabba"
Sortie: "yzzy"
Explication: "yzzy" et "abba" sont tous deux des palindromes de longueur 4, et aucun palindrome plus long n’existe. "yzzy" commence à l’indice 1, avant "abba" à l’indice 5, il remporte donc l’égalité.

Entrée: s = "abcd"
Sortie: "a"
Explication: Aucune paire de lettres n’est identique, donc chaque palindrome est constitué d’une seule lettre. Le palindrome le plus à gauche est "a".

+18 tests cachés à la soumission

Pour aller plus loin

Peux-tu trouver la réponse en temps O(n) ?

Indices

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

0 sur 3 ouverts

Solution

Un palindrome se reflète autour de son milieu, qui est soit une lettre (longueur impaire, comme "anana"), soit l’espace entre deux lettres identiques (longueur paire, comme "abba"). Vérifier chaque sous-chaîne séparément ignore cette structure et coûte O(n³). Développer chaque palindrome vers l’extérieur à partir de son milieu permet de réutiliser chaque comparaison, ce qui ramène la recherche à un temps de O(n²) et à une mémoire supplémentaire de O(1).

Vérifie chaque sous-chaîne

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Une sous-chaîne est définie par son premier indice i et son dernier indice j. Testez-la avec deux pointeurs : comparez s[i] à s[j], puis s[i+1] à s[j-1], et ainsi de suite, en vous arrêtant à la première différence. Si les pointeurs se rejoignent ou se croisent sans en trouver, la sous-chaîne est un palindrome. Gardez la plus longue trouvée.

Pour la règle de départage, parcourez les débuts de gauche à droite et ne remplacez la meilleure que si un nouveau palindrome est strictement plus long. Un palindrome ultérieur de même longueur ne remplacera donc jamais un palindrome antérieur : vous renverrez celui qui est le plus à gauche.

Cette méthode examine les n(n+1)/2 sous-chaînes, elle ne peut donc pas passer à côté de la réponse. Elle est lente, car chaque test peut parcourir la moitié de la sous-chaîne. Pour une chaîne composée de 2000 copies de a, chaque sous-chaîne est un palindrome et chaque test va jusqu'au milieu : environ n³/12 ≈ 6.7 × 10^8 comparaisons de lettres.

Algorithme

Commencez par la première lettre comme meilleure solution : début 0, longueur 1.
Pour chaque début i et chaque fin j ≥ i, comparez les lettres des deux extrémités vers le milieu jusqu’à ce qu’elles diffèrent ou que les pointeurs se rejoignent.
Si les pointeurs se sont rejoints sans désaccord, s[i..j] est un palindrome.
Si sa longueur j-i+1 est supérieure à la meilleure, enregistrez i et cette longueur.
Renvoyez la sous-chaîne au meilleur début avec la meilleure longueur.

def longestPalindrome(s):
    n = len(s)
    best_start, best_len = 0, 1
    for i in range(n):
        for j in range(i, n):
            # Compare s[i..j] from both ends toward the middle
            left, right = i, j
            while left < right and s[left] == s[right]:
                left += 1
                right -= 1
            is_palindrome = left >= right
            if is_palindrome and j - i + 1 > best_len:
                best_start, best_len = i, j - i + 1
    return s[best_start:best_start + best_len]

Tableau des palindromes par longueur

Intuition

La force brute oublie ce qu’elle a appris. Lorsqu’elle teste "anana", elle compare a avec a, puis n avec n, et la deuxième comparaison constitue tout le test de "nan", qu’elle a déjà effectué. La règle qui évite ce travail : s[i..j] est un palindrome lorsque ses deux extrémités correspondent et que la partie entre elles, s[i+1..j-1], est un palindrome. Une comparaison et une réponse mémorisée suffisent pour chaque sous-chaîne.

Mémorisez les réponses dans un tableau pal[i][j] et remplissez-le par longueur. Chaque lettre seule est un palindrome. Une sous-chaîne de deux lettres en est un lorsque les deux lettres correspondent. Pour les longueurs supérieures, appliquez la règle : l’intérieur est deux lettres plus court, donc sa case est déjà remplie.

Dans "bananas", pal[1][5] ("anana") est vrai parce que s[1] et s[5] sont tous deux des a et que pal[2][4] ("nan") est vrai. Les longueurs augmentent et les positions de départ vont de gauche à droite, donc le premier palindrome d’une nouvelle longueur record est aussi celui qui se trouve le plus à gauche pour cette longueur. Environ n²/2 cases coûtent O(1) chacune, donc le temps est O(n²) ; le prix à payer est la mémoire, 4 × 10^6 cases pour n = 2000.

Algorithme

Crée une table n × n pal, entièrement initialisée à false.
Pour chaque longueur de 1 à n et chaque début i dont la fin j = i+length-1 reste dans la chaîne, vérifie les deux lettres aux extrémités.
Marque pal[i][j] lorsqu’elles correspondent et que la longueur est au plus 2 ou que pal[i+1][j-1] est true.
Lorsqu’une case marquée a une longueur supérieure à la meilleure longueur trouvée, enregistre i et la longueur.
Renvoie la sous-chaîne à partir du meilleur début.

def longestPalindrome(s):
    n = len(s)
    # pal[i][j] is True when s[i..j] reads the same both ways
    pal = [[False] * n for _ in range(n)]
    best_start, best_len = 0, 1
    for length in range(1, n + 1):
        for i in range(n - length + 1):
            j = i + length - 1
            # Equal ends, and the part inside them is a palindrome (or too short to matter)
            if s[i] == s[j] and (length <= 2 or pal[i + 1][j - 1]):
                pal[i][j] = True
                if length > best_len:
                    best_start, best_len = i, length
    return s[best_start:best_start + best_len]

Développez autour de chaque centre

Intuition

Chaque palindrome a un centre. Un palindrome de longueur impaire comme "anana" est centré sur une lettre ; un palindrome de longueur paire comme "abba" est centré sur l’espace entre ses deux lettres centrales. Une chaîne de longueur n contient n lettres et n-1 espaces, soit 2n-1 centres possibles.

À partir d’un centre, avance d’une lettre vers l’extérieur de chaque côté tant que les deux lettres correspondent. Chaque étape prouve l’existence d’un palindrome deux lettres plus long. La première différence, ou le bord de la chaîne, met fin au parcours, et aucun palindrome plus long ne peut partager ce centre, car il contiendrait la paire de lettres différentes. Ainsi, un parcours vers l’extérieur trouve le plus long palindrome autour de chaque centre, et le plus long d’entre eux est la réponse.

Dans "bananas", commence au a d’indice 3. Les lettres aux indices 2 et 4 sont toutes deux des n, celles aux indices 1 et 5 sont toutes deux des a, et celles aux indices 0 et 6 sont b et s ; le parcours s’arrête donc à une longueur de 5. Le début est 3 - (5-1)/2 = 1, ce qui donne "anana". La même formule, center - (length-1)/2 arrondi à l’entier inférieur, fonctionne aussi pour les centres situés entre deux lettres.

Parcours les centres de gauche à droite et ne remplace le meilleur résultat que si la longueur est strictement supérieure. Deux palindromes de même longueur ont la même parité, et celui dont le centre est le plus à gauche commence plus tôt ; c’est donc le palindrome le plus à gauche qui l’emporte. Le pire cas est une chaîne composée d’une même lettre répétée : chaque centre avance jusqu’au bord le plus proche, soit environ n²/2 = 2 × 10^6 étapes pour n = 2000, et la mémoire requise est de quelques entiers.

Algorithme

Écrivez expand(left, right) : tant que les deux index se trouvent dans la chaîne et que les lettres correspondent, diminuez left et augmentez right. Retournez right-left-1.
Pour chaque centre de 0 à n-1, prenez la plus grande valeur entre expand(center, center) et expand(center, center+1).
Si cette longueur dépasse la meilleure longueur, définissez le meilleur début sur center - (length-1)/2, arrondi à l'entier inférieur, et la meilleure longueur sur cette valeur.
Retournez la sous-chaîne commençant au meilleur début et ayant la meilleure longueur.

def expand(s, left, right):
    # Grow outward while the two ends match; return the palindrome's length
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return right - left - 1


def longestPalindrome(s):
    best_start, best_len = 0, 1
    for center in range(len(s)):
        # Odd lengths grow from one letter, even lengths from the gap after it
        length = max(expand(s, center, center), expand(s, center, center + 1))
        if length > best_len:
            best_start = center - (length - 1) // 2
            best_len = length
    return s[best_start:best_start + best_len]

Pièges et cas limites

L’idée est simple, alors les bogues se cachent dans les détails : les centres entre les lettres, la longueur après le parcours, la règle en cas d’égalité et le découpage.

Ne développer qu’autour des lettres manque tous les palindromes de longueur paire. Avec "abba", cela renvoie "a" au lieu de "abba".
Le parcours s’arrête un pas après chaque extrémité, donc le palindrome est s[left+1..right-1] et sa longueur est right-left-1. Utiliser right-left+1 ajoute deux lettres qui ne correspondent pas.
Remplacer le meilleur résultat en cas de longueur égale renvoie le palindrome le plus à droite : "abba" au lieu de "yzzy" pour "xyzzyabba".
Pour un centre situé dans un intervalle, center - length/2 est décalé d’une position vers la gauche. Dans "xyzzyabba", l’intervalle après l’indice 2 a une longueur de 4, et le début est 2 - (4-1)/2 = 1, et non 0.
Les API de découpage diffèrent : C++ substr et C# Substring prennent une longueur, tandis que JavaScript substring et Java substring prennent un indice de fin.
Dans le tableau, remplir les lignes en partant de 0 pour le début fait lire pal[i+1][j-1] avant que cette valeur soit définie. Remplissez par longueur, ou parcourez les débuts en partant de la fin.

Questions fréquentes4

Quelle est la complexité temporelle de la plus longue sous-chaîne palindromique ?

L’expansion autour des centres prend un temps O(n²) et une mémoire supplémentaire O(1). L’approche par tableau prend également un temps O(n²), mais nécessite une mémoire O(n²), et vérifier chaque sous-chaîne prend un temps O(n³). L’algorithme de Manacher atteint O(n), mais les personnes qui mènent les entretiens s’y attendent rarement.

Pourquoi l’expansion autour du centre utilise-t-elle 2n-1 centres ?

Un palindrome de longueur impaire a une lettre centrale, et un palindrome de longueur paire a un espace central entre deux lettres identiques. Une chaîne de n lettres comporte n lettres et n-1 espaces entre les lettres voisines. En partant uniquement des lettres, on passe à côté de palindromes comme "abba".

Qu’est-ce que l’algorithme de Manacher ?

Il trouve le plus long palindrome autour de chaque centre en un temps total de O(n). Il conserve le palindrome qui s’étend le plus loin vers la droite jusque-là, et un centre situé à l’intérieur de celui-ci part de la réponse de son centre miroir, de sorte qu’aucune lettre n’est comparée à nouveau depuis le début. Il est utile de le connaître sous son nom ; l’expansion autour du centre est la solution que les recruteurs attendent généralement.

En quoi la plus longue sous-chaîne palindromique diffère-t-elle de la plus longue sous-séquence palindromique ?

Une sous-chaîne est une suite de lettres consécutives, tandis qu’une sous-séquence peut sauter des lettres. Dans "character", la plus longue sous-chaîne palindromique est "ara", mais "carac" est une sous-séquence palindromique de longueur 5. La version sous-séquence se résout à l’aide d’un tableau portant sur (i, j), qui élimine une extrémité lorsque les deux extrémités diffèrent.

Python

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

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

s = "bananas"

Attendu

"anana"

Longest Palindromic Substring

Fonction

Contraintes

Exemples

Indices

Solution

Vérifie chaque sous-chaîne

Tableau des palindromes par longueur

Développez autour de chaque centre

Pièges et cas limites

Questions fréquentes4

Problèmes similaires