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;
	}
}

Similar Posts

Heap Sort Algorithm

This is another very useful sorting algorithm based on Heap data structure. Read…

Quick Sort Algorithm

This algorithm is very useful for large input. And, is quite efficient one. It…

Latest Posts