CareerCup

None ever needed it, it is meaningless - but well, meaning is not what selling nowadays, snapchat is the proof. So here:

[ geeksforgeeks.org/manachers-algorithm-linear-time-longest-palindromic-substring-part-1 ]

That should solve it.

Naive solution in python. Cost (n^3). n^2 possible strings and the cost to check if each string is a palidrome is n.

def isPalindrome(s):
    return s == s[::-1]
                   
def longestPalindrome(s):
    max_length = 0
    for x in xrange(len(s)):
        for y in xrange(x+1, len(s)+1):
            if (y - x) > max_length and isPalindrome(s[x:y]):
                max_length = (y - x)
    return max_length

lhjhjkhk

Of course these questions don't have values unless very specific scaled up things need some tuning. O(n2) is common implementation that works well. Here is O(n) implementation based on Manacher's algorithm for odd-length palindromes e.g. madam (can be extended to include even-length palindromes e.g. deed - more complex, but possible)

#include <iostream>
#include <algorithm>
#include <string>
#include <map>
#include <vector>

using namespace std;

inline bool areEqualCharacters(char c1, char c2)
{
	// May be replaced with case-insensitive compare 
	if (tolower(c1) == tolower(c2))
		return true;
	return false;
}

int expand(string &s, size_t sLen, int c, int offset = 1)
{
	int left = c - offset;
	int right = c + offset;
	int start = left;
	// Assuming odd compare.
	// Logic can be expanded for palindrome of even length.
	while ((left >= 0) && (right < sLen))
	{
		if (!areEqualCharacters(s[left], s[right]))
		{
			break;
		}
		--left;
		++right;
	}
	if (left != start) {
		++left;
		--right;
		return (right - left + 1);
	}
	return 0; // Unable to expand
}

string findLargestPalindrome(string& s)
{
	size_t sLen = s.length();
	vector<int> expansion(sLen);
	multimap<int, int> sortedExpansion;
	for (int center = 0; center < sLen;)
	{
		int expandedRange = expand(s, sLen, center);
		expansion[center] = expandedRange;
		sortedExpansion.emplace(expandedRange, center);
		if (expandedRange > 0)
		{
			// Mirror right and select next center
			int halfRange = expandedRange / 2;
			int mirrorValue, rightIndex = 0, largestRight = 0;
			while (halfRange > 0) {
				mirrorValue = expansion[center - halfRange];
				rightIndex = center + halfRange;
				expansion[rightIndex] = mirrorValue;
				sortedExpansion.emplace(mirrorValue, rightIndex);
				if (expansion[largestRight] < mirrorValue)
					largestRight = rightIndex;
				--halfRange;
			}
			// Move center to next possible largest palindrome
			// or beyond current mirrored right boundary
			center = (0 != largestRight) ? largestRight: (rightIndex + 1);
		}
		else
			++center;
	}
	auto largestString = sortedExpansion.rbegin();
	if (1 < largestString->first)
	{
		pair<int, int> p = *largestString;
		string largestPalindromeSub = s.substr(largestString->second - (largestString->first/2), largestString->first);
		return largestPalindromeSub;
	}
	return "";	// No palindrome sub-string found.
}

int main()
{
	//string s = "abracadabra";
	string s = "aaaomkaraKmoa";
	string lp = findLargestPalindrome(s);
	return 0;
}