Interview Question Longest Palindromic Substring

By Fatih KABAKCI

The problem is to figure out what the longest palindromic substring is in a given string. For the basic solution which is brute force, all possible substrings are checked whether they are palindrome or not. While they are being analyzed, updated longest one is stored. For more advance solution which is expanding around the center, 2 characters (even) and 3 characters (odd) are looked for seperately. Then if something is found, the number of character that is looked for is expanded for 4, 6, 8 or 3, 5, 7 so on.

Problem #5 - Longest Palindromic Substring

Description: Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Difficulty: Medium

Solution in Java

Both Brute force and Expanding Around Center have been published the following.

Brute Force

Brute force is the basic solution for this problem. All possible substrings are tested for palindrom operation. If any substring which is longer palindrome is stored as longest. Sample has been published in Java below.

package com.fatihkabakci.Medium.LongestPalindSubStr.BruteForce;

/**
 * 
 * @author fkabakci
 * Problem Description: Given a string s, find the longest palindromic substring in s. 
 * You may assume that the maximum length of s is 1000.
 * 
 * Examples:
 * 
 * Input: "babad"
 * Output: "bab"
 * Note: "aba" is also a valid answer.
 * 
 * Input: "cbbd"
 * Output: "bb"
 * 
 * Solution:
 * Brute Force
 * 1. Look for all possible substrings and to find out whether they are palindrome
 * 2. Get the longest one
 */

public class LongestPalindromicSubstring {
	
	public boolean isPalindrome(String str) {
		return str.equals(new StringBuilder(str).reverse().toString());
	}

	public String longestPalindrome(String s) {
		if (s.isEmpty() || s.length() == 1)
			return s.intern();

		String palindrome = null;
		int longestLength = 0;

		for (int i = 0; i < s.length(); i++) {
			for (int j = i + 1; j <= s.length(); j++) {		
				if (longestLength > j - i)
					continue;

				String sij = s.substring(i, j);
				if (isPalindrome(sij)) {
					longestLength = j - i;
					palindrome = new String(sij);
				}
			}
		}
		return palindrome;
	}

	public static void main(String[] args) {
		LongestPalindromicSubstring a = new LongestPalindromicSubstring();
		String longestSubStr = a.longestPalindrome("babad");
		System.out.println(longestSubStr);
	}
}

The algorithm complexity is O(n^3) since n traveling for palindrome check, and n^2 traveling for all substrings. This complexity is considered too much by responding Time Limit Exceed on LeetCode platform.

Expanding Around Center

Expanding around center approaching provides better solution rather than brute force does. Firstly, all single substrings are accepted that they are already palindrome. The algorithm seeks for longest one by analyzing even and odd number of characters. It expands the distance every time it finds something. Let's we examine the following example.

For example when input is BAFAE, to understand how the algorithm works better, all steps have been picturized the following.

The solution has been shared in Java below.

package com.fatihkabakci.Medium.LongestPalindSubStr.ExpandAroundCenter;

/**
 * 
 * @author fkabakci
 * Problem Description: Given a string s, find the longest palindromic substring in s. 
 * You may assume that the maximum length of s is 1000.
 * 
 * Examples:
 * 
 * Input: "babad"
 * Output: "bab"
 * Note: "aba" is also a valid answer.
 * 
 * Input: "cbbd"
 * Output: "bb"
 * 
 * Solution:
 * Brute Force
 * 0. Assume that all single characters are already palindrome
 * 1. Check for two characters
 * 2. Check for three characters
 * 3. If anything found,
 * 		update and save positions,
 *      and then expand the distance by moving the lower index to the left, and higher index to the right.
 *      Keep looking for longer one.
 * 4. Get the longest one by using updated index parameters.
 */

public class LongestPalindromicSubstring {
	
	private int startIndex = 0;
	private int endIndex = 0;
	
	private int expand(char[] arr, int left, int right, int maxLength) {
		while (left >= 0 && right < arr.length && arr[left] == arr[right]) {
			int length = right - left + 1;
			// current length is higher ?
			if (length > maxLength) {
				// then set maxLength is the highest one
				maxLength = length;
				// set startIndex as left which is starting position for substring.
				startIndex = left;
				// set endIndex as right + 1, adding 1 since java.lang.String.substring() is will be used
				endIndex = right + 1;	
			}
			// expanding
			left--;
			right++;
		}
		return maxLength;
	}
	
	public String longestPalindrome(String s) {
		char[] arr = s.toCharArray();
		int length = arr.length, maxLength = 0;
		if (length > 0) {
			//  at least 1 character which is already palindrome.
			maxLength = 1;
			endIndex = 1;
		}
		for(int i = 0; i < length; i++) {
			// start with 2 characters then expand if necessary
			maxLength = expand(arr, i, i + 1, maxLength);
			// start with 3 characters then expand if necessary
			maxLength = expand(arr, i, i + 2, maxLength);
		}
		String sub = s.substring(startIndex, endIndex);
		return sub;
	}
	
	public static void main(String[] args) {
		
		LongestPalindromicSubstring o = new LongestPalindromicSubstring();
		String p = o.longestPalindrome("bafafa");
		System.out.println(p);
	}
}

The algorithm complexity is O(n^2) since it is traveled n time for getting characters, and n time too for palindromic operations..

Similar Problems

#3 Longest Substring Without Repeating Characters

#9 Palindrome Number