Minimum number of deletions to make a string palindrome

So this is a most asked question in coding interview, I have provided you the code for it and also explain how the given below code is working.

Minimum number of deletions to make a string palindrome (using Recursion)

#include <stdio.h>
#include <string.h>

#define MAX_LEN 100

// Function prototype
int minDeletions(char str[], int i, int j);

int main()
{
    char str[MAX_LEN];
    int n;

    printf("Enter a string: ");
    scanf("%s", str);

    n = strlen(str);

    printf("Minimum number of deletions required: %d\n", minDeletions(str, 0, n - 1));

    return 0;
}

// Recursive function to calculate minimum number of deletions
int minDeletions(char str[], int i, int j)
{
    // base case: string is already palindrome
    if (i >= j)
        return 0;

    // check if first and last characters match
    if (str[i] == str[j])
        return minDeletions(str, i + 1, j - 1);
    else
        // characters do not match, so try both cases: delete either first or last character
        return 1 + min(minDeletions(str, i + 1, j), minDeletions(str, i, j - 1));
}

Explanation

This program uses a recursive function, minDeletions(), to calculate the minimum number of deletions required to make a string palindrome. The function has three parameters:

• str: the input string
• i: the starting index of the string
• j: the ending index of the string

The base case of the recursion occurs when i is greater than or equal to j. In this case, the string is already a palindrome, so we return 0.

Otherwise, we check if the first and last characters of the string match. If they do, we recurse on the substring with the first and last characters removed. If they do not match, we try both cases: deleting the first character and deleting the last character. We return the minimum of these two cases.

Read: Interleaving String Problem Solution