how to efficiently get minimal number removals of characters of the string to convert it to palindrome

Question

About the question how to convert a string to palindrome with minimum number of removals of characters of the string? . I write the program to test the answer accepted. But recursion takes too much time. How can this problem be solved or improved?Below is the answer accepted:

Let dp[i, j] = minimum number of removals needed to convert the substring [i, j] to a palindrome. We have:

dp[i, i] = 0 for all i (every single character is a palindrome) To find dp[i, j], let's consider a random string. We have two possibilities:

1. The first and last characters are equal: a[i] == a[j]. In this case, we can reduce the problem to finding the minimum number of characters that need to be deleted in order to make the substring [i+1, j-1] a palindrome.

2. The first and last characters are not equal: a[i] != a[j]. In this case, we need to remove one of them. We'll remove that which leads us to a better solution.

/* remvoe the least characters to make a string be palindrome */

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

#define MAXLINE  4096

int func(char *p, int low, int high);
int min(int m, int n); // get the minimal value

int main(void)
{
    char    str[MAXLINE];
    int     ret;

    while (scanf("%s", str) != EOF) { // input in a loop
        ret = func(str, 0, strlen(str) - 1); // call func

        printf("%d\n", ret);
    }

    return 0;    
}

/* find the minimal number of characters in a string, 
 * which are needed removed to make the string be palindrome 
 */
int func(char *p, int low, int high)
{
    int     n;
    int     l;
    int     r;

    if (low >= high) {
        return 0;
    }

    if (p[low] == p[high]) { // needn't remove 
        n = func(p, low + 1, high - 1);          
    }
    else {
        l = func(p, low + 1, high);
        r = func(p, low, high - 1);
        n = min(l, r) + 1;
    } 

    return n;
}

/* return the minimal variable */
int min(int m, int n) 
{
    return (m < n ? m : n);

}

Answer 1

A key improvement is to recognize that when only one side of the string is eliminated, the other side must have a match (with a character on the other side, even if it is itself), else why not eliminate both sides?

When a character from one side is removed, seek from that side toward the other for a match of the other side's character. (A match is always be found.) This eliminates many unnecessary recursion paths.

A secondary improvement "short-circuits" as below. No need to test other combinations as they cannot improve the result.

if (left == 1) return 1;

int func(const char *p, int low, int high) {
  int n;
  int left;
  int right;

  count++;
  if (low >= high) {
    return 0;
  }

  if (p[low] == p[high]) { // needn't remove
    n = func(p, low + 1, high - 1);
  } else {
#if 0
    left = func(p, low + 1, high);
    // if (left == 0) return 1;
    right = func(p, low, high - 1);
    n = min(left, right) + 1;
#else
    int delta;
    // remove low, keep high as part of palindrome
    delta = 1;
    while (p[low + delta] != p[high])
      delta++;
    left = func(p, low + delta, high) + delta;
    if (left == 1) return 1;

    // remove high, keep low as part of palindrome
    delta = 1;
    while (p[low] != p[high - delta])
      delta++;
    right = func(p, low, high - delta) + delta;
    if (right <= 2) return right;
    n = min(left, right);

    // remove first and last
    //int both = func(p, low + 1, high-1) + 1 + (high > (low + 1));
    int both = func(p, low + 1, high - 1) + 2;
    n = min(n, both);
#endif
  }
  return n;
}

Mouse over for final result of OP's test string (Hidden in case OP does not want to see it right away.)

count = 13090 ret = 45 str = 'jfdasflkjddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddfjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj'

A minor improvement uses const. Some compliers will generate more efficient code knowing the buffer is unchanging. Better compilers may detect this anyways.

// int func(char *p, int low, int high)
int func(const char *p, int low, int high)

---

Some test driver code

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

#define MAXLINE  4096
unsigned long long count = 0;

int func(const char *p, int low, int high);
int min(int m, int n); // get the minimal value

void testfunc(const char *str) {
  count = 0;
  int ret = func(str, 0, (int) strlen(str) - 1); // call func
  printf(" count = %llu", count);
  printf(" ret = %d", ret);
  printf(" str = '%s' ++", str);
  puts("");
  fflush(stdout);
}

int main(void) {
  char str[MAXLINE];
  int ret;

  char t[] =
      "jfdasflkjdddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd"
          "ddddddddddddddfjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjjj";
  for (size_t i = 0; t[i]; i++) {
    strncpy(str, t, i);
    str[i] = 0;
    testfunc(str);
  }
  return 0;
}

int min(int m, int n) {
  return (m < n ? m : n);
}

int func(const char *p, int low, int high) {
  ...

Answer 2

you shouldn't call it recursively, because that leads to multiple execution of the same check (some range will be checked many times, when in reality only one check is required). Instead u should use a "dynamic programming" method, build from bottom to top. What that means is u need to create a two-dimensional array, dp[i][j], i<j, which stores the length of a maximum palindrome in range i to j. So if j=i+k first u proceed to build for k=0, then for k=1 and so on.