Member Avatar for varunrathi

HI EVERYONE,
I HAVE GOT A VERY INTERESTING PROBLEM THIS TIME. U HAVE TO FORM A PALINDROME OF AN ENTERED STRING. IT`S NOT THE UASUAL STUFF OF CHECKING WHETHER AN ENTERED STRING IS A PALINDROME OR NOT.
IN THIS PROGRAM, SAY IF THE GIVEN STRING IS:
"A3BCA"
THEN THE PROGRAM SHOULD FORM THE SHORTEST PALINDROME POSSIBLE BY INSERTING "CB3" AT THE SECOND LAST POSITION;
i.e; THE OUTPUT SHOULD BE
"A3BCCB3A"
OR THE OUTPUT CAN ALSO BE
"A3CBC3A"
OR

OR IF THE INPUT IS "AAMDM"
THEN THE SOLUTION IS "AAMDMAA" AND NOT "MDMAAMDM" B`COS WE HAVE TO FIND THE SHORTEST POSSIBLE PALINDROME.

SO, PLZ CAN ANY 1 HELP ME TO BEGIN IN THE RIGHT DIRECTION.

  • 5 Contributors
  • 7 Replies
  • 205 Views
  • 4 Years Discussion Span
  • Latest Post Latest Post by yellowSnow

Dani AI

Generated

Short answer and a robust approach

The task is to make the shortest palindrome by inserting characters (no deletions or reordering). A simple greedy—compare characters from the ends and, on the first mismatch, append the reverse of the remaining suffix—will produce a correct palindrome (that was the helpful starting hint from ) but it is not guaranteed to be minimal in the number of insertions. To guarantee the shortest result use dynamic programming: compute the minimum insertions for every substring and then reconstruct one optimal palindrome.

Core idea (DP recurrence)

  • Let dp[i][j] be the minimum insertions needed to make s[i..j] a palindrome.
  • If s[i] == s[j], dp[i][j] = dp[i+1][j-1].
  • Otherwise dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1]).
    Fill dp bottom-up (increasing substring length). Reconstruct by walking i and j from the ends: when characters match, put that char at both ends of the answer; when they differ, consult dp to decide whether to insert s[i] or s[j]. Time O(n^2), space O(n^2).

Example implementation (Python)

def shortest_palindrome_by_insertion(s):
    n = len(s)
    if n < 2:
        return s
    dp = [[0]*n for _ in range(n)]
    for length in range(2, n+1):
        for i in range(0, n-length+1):
            j = i + length - 1
            if s[i] == s[j]:
                dp[i][j] = dp[i+1][j-1] if i+1 <= j-1 else 0
            else:
                dp[i][j] = 1 + min(dp[i+1][j], dp[i][j-1])
    i, j = 0, n-1
    left, right = [], []
    while i <= j:
        if s[i] == s[j]:
            if i == j:
                left.append(s[i])
            else:
                left.append(s[i]); right.append(s[j])
            i += 1; j -= 1
        elif dp[i+1][j] <= dp[i][j-1]:
            left.append(s[i]); right.append(s[i]); i += 1
        else:
            left.append(s[j]); right.append(s[j]); j -= 1
    return ''.join(left) + ''.join(reversed(right))

Notes

  • This returns one shortest palindrome; multiple minimal answers may exist. Tie-breaking in the reconstruction is arbitrary but deterministic here (prefer advancing i when equal).
  • For very long strings memory can be an issue (dp is O(n^2)); if only the insertion count is needed you can reduce space, but full reconstruction requires storing DP.
  • : good that you finished the basic version; this DP upgrade gives the provably shortest palindrome. And : avoid ALL CAPS in future posts for readability.

Recommended Answers

All 7 Replies

Member Avatar for jwenting

ah, it's that time of year again.
About right, few weeks before the Christmas vacation...

P.S. posting in all caps is unlikely to get you more help. In fact it's extremely annoying and I won't read any post written that way.
P.P.S. read the posting guidelines. We're not here to do your homework for you.

Member Avatar for varunrathi

please help to initiate me. i don`t want the full work to be done

Member Avatar for jwenting

start by yourself then come back with specific questions.

Member Avatar for nvanevski

Ok, I'll just give you a hint, try to do the program by yourself. Start with matching the characters on the opposite end of the string. On the first mismatch, get the rest of the string, create the reverse string from it and insert it into the right position.

When you do this kind of programs, try to document your thinking with code-like (pseudo-code) sentences. Helps a lot with actual coding.

Member Avatar for varunrathi

Hey! NVANEVSKI,
Thanks a lot. Your suggestion made the program so easy that i have just finished doing it.

Member Avatar for jagsss16

HI EVERYONE,
I HAVE GOT A VERY INTERESTING PROBLEM THIS TIME. U HAVE TO FORM A PALINDROME OF AN ENTERED STRING. IT'S NOT THE UASUAL STUFF OF CHECKING WHETHER AN ENTERED STRING IS A PALINDROME OR NOT.
IN THIS PROGRAM, SAY IF THE GIVEN STRING IS:
"A3BCA"
THEN THE PROGRAM SHOULD FORM THE SHORTEST PALINDROME POSSIBLE BY INSERTING "CB3" AT THE SECOND LAST POSITION;
i.e; THE OUTPUT SHOULD BE
"A3BCCB3A"
OR THE OUTPUT CAN ALSO BE
"A3CBC3A"
OR

OR IF THE INPUT IS "AAMDM"
THEN THE SOLUTION IS "AAMDMAA" aND NOT "MDMAAMDM" B'COS WE HAVE TO FIND THE SHORTEST POSSIBLE PALINDROME.

SO, PLZ CAN ANY 1 HELP ME TO BEGIN IN THE RIGHT DIRECTION.

#include<stdio.h>
#include<conio.h>
#include<string.h>
int i,l=0,n,p;
char pal[10];
void main()
{
  clrscr();
  printf("Enter string:");
  scanf("%s",pal);
  l=strlen(pal);
  for(i=0;i<l-1;i++)
 {
  printf("%c",pal[i]);
 }
 for(i=l-2;i>=0;i--)
 {
  printf("%c",pal[i]);
 }
 getch();
}
Edited by mike_2000_17 because: Fixed formatting
Member Avatar for yellowSnow

This post is over four and half years old and it was SOLVED. Why are you reviving old threads.

And there's that blasted void main again.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.