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.



Follow us on Facebook and Twitter for latest update.

C Programming: Tips of the Day

Returning an array using C

You can't return arrays from functions in C. You also can't (shouldn't) do this:

char *returnArray(char array []){
 char returned [10];
 //methods to pull values from array, interpret them, and then create new array
 return &(returned[0]); //is this correct?
}

returned is created with automatic storage duration and references to it will become invalid once it leaves its declaring scope, i.e., when the function returns.

You will need to dynamically allocate the memory inside of the function or fill a preallocated buffer provided by the caller.

Dynamically allocate the memory inside of the function (caller responsible for deallocating ret)

char *foo(int count) {
    char *ret = malloc(count);
    if(!ret)
        return NULL;

    for(int i = 0; i < count; ++i) 
        ret[i] = i;

    return ret;
}

Call it like so:

int main() {
    char *p = foo(10);
    if(p) {
        // do stuff with p
        free(p);
    }

    return 0;
}

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

We are closing our Disqus commenting system for some maintenanace issues. You may write to us at reach[at]yahoo[dot]com or visit us at Facebook