Plus longue sous-séquence et sous-chaîne palindromiques

Une sous-séquence palindromique est une sous-séquence (dont les éléments ne sont pas nécessairement contigus) qui se lit de la même façon dans les deux sens. Une sous-chaîne palindromique doit être composée de caractères contigus. Pour 'bbbab', la plus longue sous-séquence palindromique est 'bbbb' (de longueur 4), tandis que la plus longue sous-chaîne palindromique est 'bbb' (de longueur 3). Ces deux problèmes nécessitent des techniques différentes malgré leurs noms similaires.

Définissez dp[i][j] comme la longueur de la plus longue sous-séquence palindromique dans s[i..j]. La récurrence est la suivante : si s[i] == s[j], alors dp[i][j] = dp[i+1][j-1] + 2 (les deux caractères identiques prolongent le palindrome intérieur). Sinon, dp[i][j] = max(dp[i+1][j], dp[i][j-1]) (ignorez le caractère gauche ou droit). Cas de base : dp[i][i] = 1 pour chaque caractère seul.

Nous remplissons le tableau LPS selon une longueur d'intervalle croissante, comme pour la DP sur intervalles générale. Pour chaque intervalle [i, j] de longueur 2 ou plus, nous vérifions si les deux caractères aux limites sont identiques et appliquons la récurrence. Le résultat final est dp[0][n-1], c'est-à-dire la LPS de la chaîne entière.

Voici une alternative élégante : la LPS de la chaîne s est égale à la LCS de s et de son inverse s[::-1]. Cela s'explique par le fait que toute sous-séquence palindromique de s est une sous-séquence commune de s et de son inverse. Cette réduction vous permet de réutiliser directement votre code de LCS. Pour 'bbbab', l'inverse est 'babbb', et leur LCS vaut 4.

La plus longue sous-chaîne palindromique doit être composée de caractères contigus. Une approche par force brute examine toutes les sous-chaînes O(n²) et vérifie chacune en O(n) time — soit O(n³) au total. Deux approches plus rapides existent : la DP sur intervalles en O(n²) time et espace, et l'expansion autour du centre en O(n²) time mais O(1) espace. En entretien, l'expansion autour du centre est préférable, car elle possède une constante plus faible et un code plus clair.

Définissez dp[i][j] = True si s[i..j] est un palindrome. Récurrence : dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]. Cas de base : dp[i][i] = True et dp[i][i+1] = (s[i] == s[i+1]). Conservez le palindrome de longueur maximale trouvé. Remplissez le tableau selon un ordre de longueur croissante. Cette méthode s'exécute en O(n²) time et utilise O(n²) espace.

L'approche d'expansion autour du centre considère chaque caractère (ainsi que chaque paire de caractères adjacents) comme un centre potentiel de palindrome et s'étend vers l'extérieur tant que les deux côtés correspondent. Il existe 2n-1 centres possibles (n pour les palindromes de longueur impaire et n-1 pour ceux de longueur paire). Chaque expansion prend au plus O(n) time, ce qui donne O(n²) au total avec O(1) espace — une solution optimale dans la plupart des contextes d'entretien.

La DP sur intervalles pour LPS utilise O(n²) espace. Lorsque vous n'avez besoin que de la longueur (et non de la sous-séquence elle-même), vous pouvez réduire l'espace en observant que dp[i][j] dépend uniquement de dp[i+1][j-1], dp[i+1][j] et dp[i][j-1]. En réutilisant les lignes et en conservant une valeur diagonale, vous pouvez atteindre O(n) espace — même si la mise en œuvre est plus complexe et rarement nécessaire en entretien.

Pour reconstruire la sous-séquence palindromique réelle, remontez dans le tableau de DP. Commencez à (0, n-1). Si s[i] == s[j], ajoutez ce caractère aux deux extrémités de votre résultat et passez à (i+1, j-1). Sinon, avancez vers celui de (i+1, j) ou (i, j-1) qui possède la plus grande valeur. Cette remontée gloutonne permet de retrouver de manière unique une sous-séquence palindromique optimale.

La LPS par DP sur intervalles et la LCS s'exécutent toutes deux en O(n²) time et O(n²) espace. L'expansion autour du centre pour la plus longue sous-chaîne palindromique utilise O(n²) time, mais seulement O(1) espace. L'algorithme de Manacher résout le problème des sous-chaînes en O(n) time et espace, mais il est suffisamment complexe pour que les recruteurs l'attendent rarement. Dans la plupart des contextes d'entretien, l'expansion autour du centre est la solution optimale attendue pour la variante des sous-chaînes.

Attention aux pièges suivants : (1) confondre une sous-séquence avec une sous-chaîne — ce sont des problèmes différents, qui ont des solutions différentes ; (2) le cas de base de la DP par intervalles pour les intervalles de longueur 2 nécessite un traitement particulier, car dp[i+1][j-1] deviendrait dp[i+1][i] (intervalle vide) ; (3) pour l’expansion autour du centre, initialisez max_len = 1 (chaque caractère isolé est un palindrome) ; et (4) lors de l’extraction du résultat, calculez start = i - (best-1)//2 afin de trouver correctement l’indice de début à partir du centre.

Vérifiez votre compréhension des concepts de Structures de données et algorithmes — Préparation aux entretiens de programmation présentés dans cette leçon.

Dans cette leçon, vous avez appris : LPS utilise une DP par intervalles avec la récurrence dp[i][j] = dp[i+1][j-1]+2 lorsque les caractères correspondent, la sous-chaîne palindromique la plus longue se résout au mieux par expansion autour du centre en O(n²) et avec un espace O(1), et LPS est égal au LCS de la chaîne et de son inverse. Nous allons ensuite aborder le partitionnement en palindromes II, qui combine une table des palindromes avec une DP 1D pour trouver le nombre minimal de coupes.