Longest Palindrome Substring in a String

Question: Find the longest palindrome substring that exists within a string.

Starting at the center of Palindrome

The brute-force way to approach this problem is to iterate through all possible substrings. This takes O(n3) time.

A better approach would be to run through our string, one character at a time, and check if it's the center of a palindrome. Upon each character, we check to see if the left and right characters are equal.

Procedure

  1. Run a loop through our string, one character at a time.
  2. Upon each character, check if it's the center of a palindrome by comparing its left and right characters.
  3. If equal, expand out one more character and check again.
  4. If not equal (or reached either ends of the string), check if this is thus far the longest palindrome substring. If so, replace the currentLongest with it.
  5. Iterate until end of string is reached.

Looks good? Great. But just one second...

Even numbered palindromes

However, we must notice one problem with this approach. If we have an even palindrome such as "HIIH", it won't get detected since there is no specific "center" of that palindrome.

To work around this, we can preprocess our string and place the "#" characters in between each letter. Thus, we will have "#H#I#I#H#". This allows us to have both even and odd-numbered palindromes.

Pre- and post-processing

Elongating the string takes linear time, so our overall time complexity will stay the same. Here is the code for both pre- and post-processing methods.

public static String preProcess(String inputString) {

	char[] charArray = new char[inputString.length() * 2 + 1];
	charArray[0] = '#';

	for (int i = 1; i < charArray.length; i += 2) {
		charArray[i] = inputString.charAt(i/2);
		charArray[i+1] = '#';
	}

	return String.valueOf(charArray);

}

public static String postProcess(String inputString) { char[] returnCharArray = new char[inputString.length() / 2]; for (int i = 1; i < inputString.length(); i += 2) { returnCharArray[i/2] = inputString.charAt(i); } return String.valueOf(returnCharArray); }

Complexity

Time: O(n2) Space: O(1)

Great, now let's code up the part that iterates through our string to find our palindrome.

public static String findLongestPal(String inputString) {

	inputString = preProcess(inputString);

	String longestPal = inputString.substring(0,1);
	int len = inputString.length();

	for (int i = 0; i < len; i++) {

		int leftCharIndex = i-1;
		int rightCharIndex = i + 1;

		while (leftCharIndex >= 0 && rightCharIndex < len) {

			if (inputString.charAt(leftCharIndex) == inputString.charAt(rightCharIndex)) {
				if (2 * (i-leftCharIndex) + 1 >= longestPal.length()) 
					longestPal = inputString.substring(leftCharIndex, rightCharIndex+1);
				leftCharIndex--; 
				rightCharIndex++;
			} else
				break;

		}

	}

	return postProcess(longestPal);
}

An O(n) Algorithm

There does exist an O(n) time problem that involves the user of Mancher's algorithm. This may be too complex to code up in an interview, but if you're interesting, follow this guide which explains the concept and implements it.

Came up with a better solution or have a question? Comment below!

Next Challenge: Removing one character