w3resource

C Exercises: Minimum number of characters to make a palindrome


29. Attractive Numbers Up to 100 Variants

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:

1

Flowchart:

C Programming Flowchart: Minimum number of characters to make a palindrome.

For more Practice: Solve these Related Problems:

  • Write a C program to generate attractive numbers up to a user-specified limit and display them in sorted order.
  • Write a C program to count and list attractive numbers up to 100 along with their defining properties.
  • Write a C program to validate whether a number is attractive by comparing its digit sum and product.
  • Write a C program to generate attractive numbers and then find the one with the highest factor count.

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.

What is the difficulty level of this exercise?

Test your Programming skills with w3resource's quiz.



Follow us on Facebook and Twitter for latest update.