Showing the minimum of letters needed for a palindrome

Question

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 <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>

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 < count) {
            int j;
            j = 0;  
            for(j = 0; j < strlen(tmp->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);
        for(j = 0; j < i; j++) {
            n_el = (elmt*)malloc(sizeof(elmt));
                n_el->string = _remove(v, j);
                n_el->next = '\0';
                root = _add(root, n_el);
        }
        return( _ncptr( v, quant-1, root, _count(root) ) );
    }
}

char* _remove(char* str, int i) {
    int j,k;
    char* nstr = (char*)malloc(strlen(str));
    nstr[0] = '\0';
    for(j = 0, k = 0; j < strlen(str); j++) {
        if(j == i) { continue; }

        nstr[k] = str[j];
        k++;
    }
    nstr[k] = '\0';
    return nstr;
}

elmt* _add(elmt* root, elmt* elm) {
    elm->next = root;
    return elm;
}

int _count(elmt* root) {
    long int l_var;
    for( l_var = 0; root && root->string; l_var++, root=root->next );
    return l_var;
}

int minfinal(char v[], int n, int i) {
    elmt* g = NULL;
    if(ispnd(v, i)) return 0;

    g = _ncptr(v, i, g, 0);

    return( strlen(v) - _last_p(g) );
}

int ispnd(char v[], int z) {
    int i, j, k;
    k = 0;
    for(i = 0, j = z; i < j; i++, j--) {
        if(v[i] != v[j]) {
            k = 1;
            break;
        }
    }
    return !k;
}

int _last_p(elmt* root) {
    int l_var = 0;
    for(; root; root=root->next ) {
          if(strlen(root->string) == 0) continue;
        if(!ispnd(root->string, strlen(root->string)-1)) continue;
        l_var = max( l_var, strlen(root->string) );
    }
    return l_var;
}

int __exist (elmt* lstt, char* str, int h) {
    int i,j;
    for(j=0; lstt, j <= h; lstt = lstt->next, j++ ) {
        i = strcmp(lstt->string, str);

        if(!i) return 1;        
    }
    return 0;
}

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

Answer 1

(Previous Answer removed)

UPDATE:

Now that I understand the problem better, I see that my previous answer is no good. I think you need a new algorithm. What you have currently is getting into a combinatorial explosion. Try using a string difference algorithm against the reversed string. For example:

input: abca

reversed: acba

difference:

abc a
a cba

So you can now see that you need to insert one letter to make the string match the reversed string. String differences can be determined relatively efficiently using dynamic programming.

Here is another example:

input: tostotor

reversed: rototsot

difference:

t ostot or
 ro totso t

So three letters are needed to make them match.

UPDATE:

You can find more information on how to determine the differences between strings here: https://stackoverflow.com/questions/208094/how-to-find-difference-between-two-strings

Answer 2

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;

}

Answer 3

I think your question could be stated as:

• Determine the minimum number of letters to be added to a given string in order to make it into a palindrome.

You can do some work analytically. I'll use upper-case letters A, B, C, ... for the given letters; I'll use lower-case letters a, b, c for those added to make a palindrome.

1. For an L-character string, the maximum number of characters that must be added is L-1.
2. In general, there are numerous ways to make a palindrome from a string.
3. Any single character is already a palindrome (L-1 = 0).
4. For a two-character string, there are two cases:
   • AA (0 to add; it is already a palindrome).
   • AB (1 to add — bAB or ABa).
5. For a three-character string, there are four five cases:
   • ABC (2 to add — cbABC).
   • AAB (1 to add — bAAB).
   • ABB (1 to add — ABBa).
   • ABA (0 to add; it is already a palindrome).
   • AAA (0 to add; it is already a palindrome).
6. For a four-character string, there are at least ten cases:
   • ABCD (3 to add — dcbABCD).
   • AABC (2 to add — cbAABC).
   • ABAC (1 to add — cABAC).
   • ABCA (1 to add — ABCbA).
   • ABBA (0 to add; it is already a palindrome).
   • ABAA (1 to add — ABAbA).
   • ABAB (1 to add — bABAB).
   • ABBB (1 to add — ABBBa).
   • AAAA (0 to add; it is already a palindrome).
   • AABB (2 to add — bbAABB).

Starting with these cases, we can see that:

• Check whether the pattern is a palindrome.
  • If yes, the number of characters to add is 0.
• Given the length, L, and the number of distinct characters, D,
  • If L = D, then you need to add L-1 characters.
• Otherwise, you can lop off the last character, make an palindrome from the L-1 character string, and add the last character again at front and back.
  • That's a nice recursive function.
  • The question is, does that add the minimum characters each time?

Let's revisit the case of L=4. X will be the number of extra characters required.

• ABCD
  • Drop D, palindrome from ABC (L=3, D=3)
  • Drop C, palindrome from AB (L=2, D=2)
    • Drop B, palindrome from A (L=1, D=1)
    • A is a palindrome ⟶ A (X=0)
    • Add B to front and back ⟶ bAB (X=1)
  • Add C to front and back ⟶ cbABC (X=2)
  • Add D to front and back ⟶ dcbABCD (X=3)
• AABC
  • Drop C, palindrome from AAB (L=3, D=2)
  • Drop B, palindrome from AA (L=2, D=1)
    • AA is a palindrome ⟶ AA (X=0)
  • Add B to front and back ⟶ bAAB (X=1)
  • Add C to front and back ⟶ cbAABC (X=2)
• ABAC
  • Drop C, palindrome from ABA (L=3, D=2)
  • ABA is a palindrome ⟶ ABA (X=0)
  • Add C to front and back ⟶ cABAC (X=1)
• ABBA
  • ABBA is a palindrome ⟶ ABBA (X=0)
• ABAA
  • Drop A, palindrome from ABA (L=3, D=2)
  • ABA is a palindrome ⟶ ABA (X=0)
  • Add A to front and back ⟶ aABAA (X=1)
• ABAB
  • Drop B, palindrome from ABA (L=3, D=2)
  • ABA is a palindrome ⟶ ABA (X=0)
  • Add B to front and back ⟶ BABAB (X=1)
• AAAA
  • ABBA is a palindrome ⟶ ABBA (X=0)
• AABB
  • Drop B, find palindrome from AAB (L=3, D=2)
  • Drop B, find palindrome from AA (L=2, D=1)
    • AA is a palindrome ⟶ AA (X=0)
  • Add B to front and back ⟶ bAAB (X=1)
  • Add B to front and back ⟶ bbAABB (X=2)

So far, so good...but there are two cases not treated:

• ABBB
  • In this example, dropping the last character is bad; it leads to bbbABBB, which is much longer than what you get if you drop the first character (namely ABBBa).
• ABCA
  • In this example, if you go about dropping the last character, you also end up with a much longer string than is necessary.

How can we refine things?

If the first and last character are the same (but the string is not a palindrome), then drop first and last character, find a palindrome for the shorter string, and then reinstate the first and last. For the ABCA example, that gives:

• ABCA
  • Drop leading and trailing A; palindrome from BC (L=2, D=2)
  • Drop C; palindrome from B (L=1, D=1)
    • B is a palindrome ⟶ B (X=0)
  • Add C at front and back ⟶ cBC (X=1)
  • Add A at front and back ⟶ AcBCA (X=1 — because we removed 2 and restored 2)

That still leaves the ABBB example causing grief. We can note that AAAB is very similar to ABBB, but AAAB would work fine with the algorithm originally proposed, producing BAAAB (X=1).

Maybe the trick is to find the longest sequence of a single character repeating at either end. If the longer of these is L/2 or greater, then you simply add the other part as a 'mirror' of itself. With the AAAB and ABBB cases:

• The longest repeat is 3 (AAA or BBB); and that's more than L/2, so the other part is added as a mirror of itself (but a mirror of 1 letter is that letter).
• AAAB adds the B in mirror, producing BAAAB (X=1).
• ABBB adds the A in mirror, producing ABBBA (X=1).
• Applied to AABB, there are two different 2-letter sequences, which are both L/2 long; it is arbitrary which is processed, and you end up with either BBAABB or AABBAA (X=2).

Looking at a longer sample, what about AACADEFFFFABA?

• The strings start and end with A; remove it and find a palindrome for ACADEFFFFAB.
  • Arbitrarily drop B; find a palindrome for ACADEFFFFA.
  • The strings start and end with A; find a palindrome for CADEFFFF.
    • There's a run of 4 F's at the end; that's L/2.
    • Add the mirror of CADE to give a palindrome ⟶ CADEFFFFEDAC (X=4)
  • Add A to both ends ⟶ ACADEFFFFEDACA (X=4)
  • Add B to both ends ⟶ BACADEFFFEDACAB (X=5)
• Add A to both ends ⟶ ABACADEFFFFEDACABA (X=5)

That seems to be about right...

Let's look at another longer sample:

• ABCDEFCBA
  • Drop the leading and trailing A's; find a palindrome for BCDEFCB.
  • Drop the leading and trailing B's; find a palindrome for CDEFC.
    • Drop the leading and trailing C's; find a palindrome for DEF.
    • Drop the F; find a palindrome for DE.
      • Drop the E; find a palindrome for D.
      • D is a palindrome ⟶ D (X=0).
      • Add E to front and back ⟶ EDE (X=1).
    • Add F to front and back ⟶ FEDEF (X=2).
    • Add C to front and back ⟶ CFEDEFC (X=2).
  • Add B to front and back ⟶ BCFEDEFCB (X=2).
  • Add A to front and back ⟶ ABCFEDEFCBA (X=2).

That too looks about right.

From here, I think it is a SMOP (Simple Matter of Programming).

---

[Later] There is probably still some refinement required...

Consider:

CABLEWASIEREISAWELBA (C Able Was I Ere I Saw Elba)

Clearly, the minimum change is to add a C to the end:

CABLEWASIEREISAWELBAc

When I first wrote up the 'longest repeat' criterion, I had 'longest palindrome', and that was probably a better choice. In this case, the longest palindrome from the end is clearly everything except the leading C, and then you end up with the minimum change. A repeat is a special case of palindrome, of course.

It does lead to the question of what happens with:

XYZABLEWASIEREISAWELBAOBSEQUIOUSNESS

There, you have a 17-letter anagram (Able ...) with 16 letters surrounding it. Does that help at all? A little. As you strip off the end characters (from OBSEQUIOUSNESS), you eventually end up with the anagram exposed, at which point you generate:

XYZABLEWASIEREISAWELBAzyx

and then you add back the OBSEQUIOUSNESS to yield:

ssensuoiuqesboXYZABLEWASIEREISAWELBAzyxOBSEQUIOUSNESS

So, the longest trailing or leading palindrome refinement seems to be about right.

How should the tests be prioritized? Should the leading/trailing palindrome be found before the leading/trailing same letter? Consider:

AABLEWASIEREISAWELBA (A Able Was I Ere I Saw Elba)

The leading and trailing letters are the same, but there's the humongous trailing anagram.

If you drop the leading and trailing A, then you process:

ABLEWASIEREISAWELB

The leading/trailing letters are different, so the trailing palindrome is spotted, and you end up with:

AABLEWASIEREISAWELBaA

If you did the trailing palindrome first, you end up with essentially the same answer:

AABLEWASIEREISAWELBAa

So, maybe the sequencing is not critical. The common letter at the end is simpler than 'the longest leading/trailing palindrome', so that makes sense as the test to perform first, unless someone devises an example where it leads to the wrong answer.

Answer 4

Even though I dont really understand C

Do you know about Levenshtein distance? It's very fast

It's just to find de minimum edit distance between 2 strings

I tried to pass the reversed string and curiously I got a result that was the double from what I espected. But taking a look seems like a rule that by dividing the result by 2 it gives the answer I want.

But take care as soon as I'm not sure of what you are trying to get I might be wrong because that calculation of distance considers insertions and deletions at any positions not only begin and end.

And if you are interested only in insertions you probably would like to remove the part of deletions from Levensthein algorithm

some tests I did (considering insertions, deletions AND replacements):

AAAA = 0

AAAB = 1

AABB = 2

ABBA = 0

ABAB = 1