#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