C Exercises: Minimum number of characters to make a palindrome

Last update on December 20 2024 13:20:07 (UTC/GMT +8 hours)

Write a C program to find the minimum number of characters that must be inserted into a given string with no whitespace characters to make it a palindrome.

Note: For example, if str1 = "pps", we can change the string to "spps", adding only 1 character.

Sample Input: pps
Output: 1

C Code:

#include<stdio.h>
#define max(a,b) (a>b?a:b)
int void main()
 {
    int t,len,i,j;
    char str1[] = "pps";
    int dp[2][10000];
    //len=fs(str1);
    len = 3;
    for(i=0;i<=len;i++) dp[0][i]=dp[1][i]=0;
        for(i=len-1;i>=0;i--)
        {
            for(j=1;j<=len;j++)
            {
                if(str1[i]==str1[j-1]) dp[1][j]=dp[0][j-1]+1;
                else dp[1][j]=max(dp[0][j],dp[1][j-1]);
            }
            for(j=0;j<=len;j++)
            {
                dp[0][j]=dp[1][j];
            }
        }
        printf("%d\n",len-dp[1][j-1]);
    return 0;
}

Sample Output:

Flowchart:

C Programming Code Editor:

Contribute your code and comments through Disqus.

Previous C Programming Exercise: First missing +ve integer in unsorted array.
Next C Programming Exercise: Prime number in strictly ascending decimal digit order.