Longest Palindrome Substring - Leet Code Solution

August 27, 2019

Problem Statement

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

Brute Force Solution

Find all substrings of a string
Check if that substring is a palindrome string
Keep a track of longest palindrome string found so far Simple!

Code

public class Q5_LongestPalindromeSubstring_Simple {
	private String str;
	
	public Q5_LongestPalindromeSubstring_Simple(String str) {
		this.str = str;
	}
	
	private boolean isPalindrome(String s) {
		int lastIndex = s.length()-1;
		int startIndex = 0;
		while (startIndex < s.length() && lastIndex >= 0) {
			if (s.charAt(startIndex) != s.charAt(lastIndex)) {
				return false;
			}
			startIndex ++;
			lastIndex --;
		}
		return true;
	}
	
	public String longestPalindrome() {
		String max = "";
		
		//generate all substrings
		for (int i=0; i<this.str.length(); i++) {
			for (int j=i+1; j<this.str.length(); j++) {
				String substring = this.str.substring(i, j);
				if (this.isPalindrome(substring)) {
					if (max.length() < substring.length()) {
						max = substring;
					}
				}
			}
		}
		
		return max;
	}
}

Runtime Complexity

It is O(n^3)

O(n^2) in find all substrings
For every substring, find out if it is a palindrome - O(n)

Optimized Solution

For optimized solutions, we should go deeper into the requirements. What is palindrome. It can be found in two ways:

Centered around a single character. Length will be odd. Example: abc
Centered around two characters. Length will be even. Example: abba

The solution is around starting from the one element, and try to expand it from both sides. Expand it till you find same character.

Algorithm

Iterate over string
Try to expand it in two ways. Around single character and around two characters
Keep track of max found palindrome substring

Code

public class Q5_LongestPalindromeSubstring_Optimized {
	private String str;
	
	public Q5_LongestPalindromeSubstring_Optimized(String str) {
		this.str = str;
	}
	
    //expanding around elements passed
	private String findPalindrome(int startIndex, int endIndex) {
		String palindrome = "";
		while (startIndex >= 0 && endIndex < this.str.length() && this.str.charAt(startIndex) == this.str.charAt(endIndex)) {
			palindrome = this.str.substring(startIndex, endIndex+1);
			startIndex --;
			endIndex ++;
		}
		
		return palindrome;
	}
	
	public String longestPalindrome() {
		String max = "";

		for (int i=0; i<this.str.length()-1; i++) {
			String s1 = this.findPalindrome(i, i);
			String s2 = this.findPalindrome(i,  i+1);
			
			String maxOfTwo = s1.length() > s2.length() ? s1 : s2;
			if (max.length() < maxOfTwo.length()) {
				max = maxOfTwo;
			}
		}
		
		return max;
	}
}