## Given a string S, find the longest palindromic substring in S.

For example,

S = “caba".

S = “caba".

The longest palindromic substring is “aba”.

Algorithm:

Algorithm:

- Palindrome mirrors around center and there are 2N-1 such centers in string. The reason is center of palindrome can be in between two letters(for even length string) or the letter itself (for odd length string).
- Expand a palindrome around its center in both direction and look for maximum possible palindrome (O(n) time).
- If the length of string is odd, the center would be letter, therefore repeat the step 2 for each letter and update maximum palindrome on the way.

- If the length of string is even, the center would be between two letters, therefore repeat the step 2 for each such center and update the maximum palindrome on the way.
- Since there are O(N) such centers, time complexity would be O(n
^{2}).

// O(n*n) time complexity and O(1) space algorithm

#include<stdio.h>

#include<string.h>

void longestpalindrome(char *str);

int main()

{

char *str = "abacba";

int i;

longestpalindrome(str);

scanf("%d", &i);

}

void longestpalindrome(char *str) {

int length = strlen(str);

printf("%d\n", length);

int i,j,k;

int start,end,max=0,curr;

if(length == 0) {printf("string null"); return;}

if(length%2!=0) { //if string is of odd length

for(i=0;i<length-1;i++) {

j=k=i;

while(j>0 && k<length-1 && str[--j]==str[++k]);

curr = k-j+1;

if(curr > max) {

max = curr;

start = j;

end = k;

}

}

for(i=start;i<=end;i++) printf("%c", str[i]);

printf("\n");

}

else { //if string is of even length

for(i=0;i<length-1;i++) {

if(str[i]==str[i+1]) {

j=i;

k=i+1;

while(j>=0 && k<=length-1 && str[j--]==str[k++]);

curr = k-j-1;

if(max < curr) {

max = curr;

start = j+1;

end = k-1;

}

}

for(i=start;i<=end;i++) printf("%c", str[i]);

printf("\n");

}

}

}

####
*// **Time Complexity:* O(n^{2})

*Time Complexity:*

####
*// **Space Complexity:* O(1)

*Space Complexity:*

There are some bugs in your code... for example

ReplyDeleteFor even sized strings, you are assuming the longest palindrome will always have a center formed of 2 letters... take your example

abacba the longest palindrome there is "aba"... but your algorithm will try to find a str[i]==str[i+1] and will never find it...

One possible fix, could be, search the whole string for two-letters centered palindromes... and then look again the string for single-letter centered palindrome... and get the longest one...