Pour déterminer le nombre de sous-chaînes palindromes dans une chaîne, où chaque caractère individuel est également considéré comme une sous-chaîne palindrome, on peut utiliser la programmation dynamique. La stratégie consiste à identifier toutes les sous-chaînes palindromes et à les compter.

Compter les sous-chaînes palindromes avec la programmation dynamique

On définit un tableau dnyamique memo[debut][fin] pour indiquer si la sous-chaîne allant de l'indice debut à fin est un palindrome, avec debut inférieur ou égal à fin. Lorsque les caractères aux extrémités diffèrent, la sous-chaîne n'est pas un palindrome. S'ils sont identiques, on distingue trois cas : si debut égale fin, c'est un palindrome ; si debut + 1 égale fin, c'est aussi un palindroem ; sinon, la valeur dépend de memo[debut+1][fin-1]. En initialisant le tableau, on ne remplit que la partie supérieure à la diagonale principale. Enfin, on additionne les entrées où memo[debut][fin] est vrai pour obtenir le résultat.

class Solution {
public:
    int compterSousChainesPalindromes(string chaine) {
        int taille = chaine.size();
        int compteur = 0;
        vector<vector>> memo(taille, vector<bool>(taille, false));
        for (int debut = taille - 1; debut >= 0; debut--) {
            for (int fin = debut; fin < taille; fin++) {
                if (chaine[debut] != chaine[fin]) {
                    memo[debut][fin] = false;
                } else {
                    memo[debut][fin] = (debut + 1 < fin) ? memo[debut + 1][fin - 1] : true;
                }
                if (memo[debut][fin]) {
                    compteur++;
                }
            }
        }
        return compteur;
    }
};</bool></vector>

La complexité temporelle est O(N²) et l'espace mémoire est O(N²).

Trouver la plus longue sous-chaîne palindrome

On peut adapter la méthode précédente en suivant la longueur maximale et l'indice de début. En utilisant la même table dynamique, si memo[debut][fin] est vrai, on compare la longueur actuelle fin - debut + 1 avec la longueur maximale enregistrée, et on met à jour le début si nécessaire. La sous-chaîne est ensuite extraite avec substr.

class Solution {
public:
    string plusLonguePalindrome(string chaine) {
        int taille = chaine.size();
        vector<vector>> memo(taille, vector<bool>(taille));
        int longueur = 0, position = 0;
        for (int debut = taille - 1; debut >= 0; debut--) {
            for (int fin = debut; fin < taille; fin++) {
                if (chaine[debut] == chaine[fin]) {
                    memo[debut][fin] = (debut + 1 < fin) ? memo[debut + 1][fin - 1] : true;
                }
                if (memo[debut][fin] && longueur < fin - debut + 1) {
                    longueur = fin - debut + 1;
                    position = debut;
                }
            }
        }
        return chaine.substr(position, longueur);
    }
};</bool></vector>

Cette approche a également une complexité temporelle de O(N²) et spatiale de O(N²).

Une alternative plus efficace est l'algorithme d'expansion centrale, qui a une complexité temporelle de O(N²) mais spatiale de O(1). On parcourt chaque caractère comme centre potentiel, et on étend vers l'extérieur pour les palindromes de longueur impaire et paire, en comparant les caractères symétriques.

class Solution {
public:
    string plusLonguePalindrome(string chaine) {
        int taille = chaine.size();
        int longueurMax = 0, debutMax = 0;
        for (int pos = 0; pos < taille; pos++) {
            int gauche = pos, droite = pos;
            while (gauche >= 0 && droite < taille && chaine[gauche] == chaine[droite]) {
                gauche--;
                droite++;
            }
            if (longueurMax < droite - gauche - 1) {
                longueurMax = droite - gauche - 1;
                debutMax = gauche + 1;
            }
            gauche = pos - 1;
            droite = pos;
            while (gauche >= 0 && droite < taille && chaine[gauche] == chaine[droite]) {
                gauche--;
                droite++;
            }
            if (longueurMax < droite - gauche - 1) {
                longueurMax = droite - gauche - 1;
                debutMax = gauche + 1;
            }
        }
        return chaine.substr(debutMax, longueurMax);
    }
};

Partition en palindromes IV

Pour vérifier si une chaîne peut être divisée en trois sous-chaînes palindromes, on peut imaginer effectuer deux coupes à des indices i et j, créant ainsi trois parties : [0, i-1], [i, j], et [j+1, n-1], où n est la longueur de la chaîne. L'approche consiste à itérer sur les positions possibles des coupes et à vérifier si chaque partie est un palindrome, par exemple en utilisant une méthode de pré-calcul pour les palindromes.