Minimum Insertions to Make Palindrome

This program finds minimum insertions to make string palindrome.

Problem Statement

Write a Java program to find minimum insertions to make "abcda" palindrome.

Source Code

1 public class MinInsertionsPalindrome {
2 public static void main(String[] args) {
3 System.out.println("Eduinq Min Insertions Palindrome");
4 String str="abcda";
5 int n=str.length();
6 int[][] dp=new int[n][n];
7 for(int gap=1;gap<n;gap++){
8 for(int i=0,j=gap;j<n;i++,j++){
9 if(str.charAt(i)==str.charAt(j)) dp[i][j]=dp[i+1][j-1];
10 else dp[i][j]=1+Math.min(dp[i+1][j],dp[i][j-1]);
11 }
12 }
13 System.out.println("Minimum insertions = "+dp[0][n-1]);
14 }
15 }

Program Output

Eduinq Min Insertions Palindrome
Minimum insertions = 2

Explanation

DP table compares characters at ends. - Insertions counted to form palindrome. - Together finds minimum insertions. Conclusion: Shows how to find minimum insertions to make string palindrome.

Quick Links to Explore