w3resource

C Exercises: Minimum number of characters to make a palindrome

C Programming Challenges: Exercise-29 with Solution

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.

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.



Share this Tutorial / Exercise on : Facebook and Twitter

C Programming: Tips of the Day

What's an object file in C?

An object file is the real output from the compilation phase. It's mostly machine code, but has info that allows a linker to see what symbols are in it as well as symbols it requires in order to work. (For reference, "symbols" are basically names of global objects, functions, etc.)

A linker takes all these object files and combines them to form one executable (assuming that it can, i.e.: that there aren't any duplicate or undefined symbols). A lot of compilers will do this for you (read: they run the linker on their own) if you don't tell them to "just compile" using command-line options. (-c is a common "just compile; don't link" option.)

Ref : https://bit.ly/3CbzF8M