To find the max palindrome in a given string

#include <iostream>
#include <string>
#include <assert.h>

using namespace std;

/*
 * Algo:
 * find the sequence where two equal letters are adjacent or apart by one letter
 * example: "aa", "aba"
 * expand the sequence while the letters at prev and next of the sequence are equal
 *
 * maintain the max palindrome encountered so far
 *
 * Complexity: best O(n) and worst O(n^2)
 */

string largestPalindrome(string s) {

int i, j, k, len = s.length(), m = 0;
string ret(1, s[0]);

for (i = 1; i < len; ++i) {

if (s[i - 1] == s[i]) {

j = i - 2;
k = i + 1;

//expand the sequence
while (j >= 0 && k < len && s[j] == s[k]) {
j--, k++;
}

//compare with prev max
if (m < (k - j - 1) ) {
m = k - j - 1;
ret = s.substr(j + 1, m);
}
}

if ( (i + 1 < len) && s[i - 1] == s[i + 1]) {

j = i - 2;
k = i + 2;

//expand the sequence
while (j >= 0 && k < len && s[j] == s[k]) {
j--, k++;
}

//compare with prev max
if (m < (k - j - 1) ) {
m = k - j - 1;
ret = s.substr(j + 1, m);
}
}
}

return ret;
}

int main() {
assert(largestPalindrome("a") == "a");
assert(largestPalindrome("sa") == "s");
assert(largestPalindrome("aa") == "aa");
assert(largestPalindrome("aaa") == "aaa");
assert(largestPalindrome("aba") == "aba");
assert(largestPalindrome("abba") == "abba");
assert(largestPalindrome("aaaa") == "aaaa");
assert(largestPalindrome("aaaaa") == "aaaaa");
assert(largestPalindrome("aabaa") == "aabaa");
assert(largestPalindrome("sambasiva") == "s");
assert(largestPalindrome("sambabmiv") == "mbabm");
assert(largestPalindrome("saaasr") == "saaas");
assert(largestPalindrome("saasr") == "saas");

cout<< "All tests passed" << endl;
}
Advertisements

One thought on “To find the max palindrome in a given string

  1. Good post. Here is little optimization.1. After while loops that verify prev and next characters successively, we can check whether entire string is palindrome. Add the checkif( j == -1 && k == len )after the while loop.2. It is worth to mention why the size of valid palindrome at any instance is (k – j – 1), as the valid indices are (j + 1, k – 1).3. Isn't suffix tree approach gives O(n) worst case at the expense of more memory?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s