Énoncé du problème

Soit une chaîne de caractères. Une chaîne est dite palindromique lorsqu'elle est identique lue de gauche à droite et de droite à gauche (ex: "radar"). L'bojectif est de déterminer le nombre minimal d'insertions de caractères nécessaires pour transformer une chaîne quelconque en palindrome. Les insertions peuvent s'effectuer à n'importe quelle position.

Approche de résolution

La solution repose sur une observation clé : le nombre minimal d'insertions équivaut à la longueur de la chaîne moins la longueur de sa plus longue sous-séquence palindromique (LPS). La LPS représente l'ensemble maximal de caractères déjà en position symétrique. Les caractères absents de cette séquence nécessitent une insertion de leur symétrique.

Mécanisme du tableau dynamique

Un tableau bidimensionnel lpsDP est utilisé où lpsDP[i][j] stocke la longueur de la LPS pour la sous-chaîne entre les indices i et j.

Relation de récurrence

Si s[i] == s[j]:
    Si j - i == 1: 
        lpsDP[i][j] = 2
    Sinon:
        lpsDP[i][j] = lpsDP[i+1][j-1] + 2
Sinon:
    lpsDP[i][j] = max(lpsDP[i+1][j], lpsDP[i][j-1])

Initialisation

for (int i = 0; i < taille; i++) {
    lpsDP[i][i] = 1; // Tout caractère unique est un palindrome
}

Parcours du tibleau

Le remplissage s'effectue par longueur croissante des sous-chaînes :

for (int longueur = 2; longueur <= taille; longueur++) {
    for (int debut = 0; debut <= taille - longueur; debut++) {
        int fin = debut + longueur - 1;
        // Application de la relation de récurrence
    }
}

Exemple illustré : Chaîne "Ab3bd"

1. Initialisation : Tous les éléments diagonaux à 1
2. Sous-chaînes de longueur 2 :
   • (A,b) → max(1,1) = 1
   • (b,3) → max(1,1) = 1
   • (3,b) → max(1,1) = 1
   • (b,d) → max(1,1) = 1
3. Sous-chaînes de longueur 3 :
   • (A,b,3) → max(lpsDP[1][2], lpsDP[0][1]) = max(1,1) = 1
   • (b,3,b) → lpsDP[1][2] + 2 = 1 + 2 = 3
   • (3,b,d) → max(lpsDP[3][3], lpsDP[2][3]) = max(1,1) = 1
4. Résultat final : lpsDP[0][4] = 3 → Insertions minimales = 5 - 3 = 2

Implémentation Java

import java.util.Scanner;

public class InsertionsPalindromeMinimales {
    public static int calculerInsertionsMinimales(String chaine) {
        int taille = chaine.length();
        int[][] lpsDP = new int[taille][taille];
        
        for (int i = 0; i < taille; i++) {
            lpsDP[i][i] = 1;
        }
        
        for (int longueur = 2; longueur <= taille; longueur++) {
            for (int debut = 0; debut <= taille - longueur; debut++) {
                int fin = debut + longueur - 1;
                char caracGauche = chaine.charAt(debut);
                char caracDroit = chaine.charAt(fin);
                
                if (caracGauche == caracDroit) {
                    lpsDP[debut][fin] = (longueur == 2) ? 2 : lpsDP[debut+1][fin-1] + 2;
                } else {
                    lpsDP[debut][fin] = Math.max(lpsDP[debut+1][fin], lpsDP[debut][fin-1]);
                }
            }
        }
        
        return taille - lpsDP[0][taille-1];
    }
    
    public static void main(String[] args) {
        Scanner lecteur = new Scanner(System.in);
        String entree = lecteur.nextLine();
        System.out.println(calculerInsertionsMinimales(entree));
    }
}