www.fatihkabakci.com

Personal Website and Computer Science TUR EN

Interview Question Longest Palindromic Substring

Last update: 11/15/2016 1:45:00 AM

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

There has been no comment yet

Name:


Question/Comment
   Please verify the image




The Topics in Computer Science

Search this site for





 

Software & Algorithms

icon

In mathematics and computer science, an algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.

Programming Languages

icon

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer. It can be used to create programs to control the behavior of a machine. Java,C, C++,C#

Database

icon

A database is an organized collection of data. The data are typically organized to model aspects of reality in a way that supports processes requiring information.

Hardware

icon

Computer hardware is the collection of physical elements that constitutes a computer system. Computer hardware refers to the physical parts or components of a computer such as the monitor, memory, cpu.

Web Technologies

icon

Web development is a broad term for the work involved in developing a web site for the Internet or an intranet. Html,Css,JavaScript,ASP.Net,PHP are one of the most popular technologies. J2EE,Servlet, JSP,JSF, ASP

Mobile Technologies

icon

Mobile application development is the process by which application software is developed for low-power handheld devices, such as personal digital assistants, enterprise digital assistants or mobile phones. J2ME

Network

icon

A computer network or data network is a telecommunications network that allows computers to exchange data. In computer networks, networked computing devices pass data to each other along data connections.

Operating Systems

icon

An operating system is software that manages computer hardware and software resources and provides common services for computer programs. The OS is an essential component of the system software in a computer system. Linux,Windows

Computer Science

icon

Computer science is the scientific and practical approach to computation and its applications.A computer scientist specializes in the theory of computation and the design of computational systems.