Showing the minimum of letters needed for a palindrome

This shows the minimum of letters needed for a palindrome. It needs tweaking since it works fine for words 1-9 characters, but becomes slow for words with 10-12 characters, and for 13+ characters it really takes a lot of time. Any help is appreciated.

```
#include
#include
#include
#include

typedef struct _el {
char ch;
struct _el* next;
} lst;

typedef struct _lst {
char* string;
struct _lst* next;
} elmt;

char _remove(char, int);
int min(int , int);
elmt _ncptr(char [], int, elmt, int );
int minfinal(char [], int, int );
elmt _add(elmt root, elmt* elm);
int _count(elmt* root);
int _last_p(elmt* root);
int ispnd(char [], int);
int __exist (elmt root, char str, int h);
int max(int, int);
lst add(lst root, char n);
int exist(lst* root, char n);

int main() {
int l, min;
char b[50];
printf("Insert the word:");
scanf("%s", b);
l = strlen(b) - 1;
printf("%d letters needed.\n", minfinal(b, 0, l));
_getch();
return 0;
}

int min(int a, int b) {
return ((a>b) ? b : a);
}

elmt _ncptr(char v[], int quant, elmt root, int count) {
int cnt_, lvar;
int len = strlen(v)-1;
if(!root) {
root = (elmt*)malloc(sizeof(elmt));
root->string = (char*)malloc(len+1);
strcpy(root->string, v);
root->next = '\0';
}
if(quant == 0) return root;
if(count > 0) {
int i;
elmt n_el, tmp = root;
i = 0;
while(i string); j++) {
n_el = (elmt*)malloc(sizeof(elmt));
n_el->string = _remove(tmp->string, j);
n_el->next = '\0';

if(__exist(root, n_el->string, i+j+1)) continue;
root = _add(root, n_el);
}
tmp = tmp->next;
i++;
}
return( _ncptr( v, quant-1, root, _count(root)-count ) );
}
else {
//MAYBE IT's FIRST CALL OF THE FUNCTION
int i,j;
elmt* n_el;
i = strlen(v

This is an obvious candidate: (there are more lines containing this anti-pattern):

for(j = 0, k = 0; j < strlen(str); j++) {...}

Will result in the strlen being called on every iteration, nmaking the whole thing an O(N*N) operation.

A better way to do the same would be:

size_t len,j,k;

len = strlen(str);
for (j=k=0; j < len;j++) {...}

Next:

char* _remove(char*, int);
elmt* _ncptr(char [], int, elmt*, int );
elmt* _add(elmt* root, elmt* elm);
int _count(elmt* root);
int _last_p(elmt* root);
int __exist (elmt* root, char* str, int h);

Identifiers with leading underscores are reserved for the implementation and / or the library.

In short: don't use them (unless you are implementing the implemnetation or the library, but in that case you would not ask this question, methinks)

Next: the _remove function is terrible. I malloc() one byte too short, calls strlen() at every heartbeat, and ignores the existing string functions.

char *newremove(char *org, size_t pos) {
    size_t len;
    char *new;

    len =  strlen(org) 
    new = malloc(1+len);

    if (pos < len) {
      memcpy(new, org, pos);
      memcpy(new+pos,org+pos+1, len-pos);
      }

    else {
      memcpy(new, org, len+1);
      }

return new;

}

StackExchange Code Review Q#10896, answer score: 3