Longest Palindromic Substring

Algorithm/Insights

1. Initialize a palindrome boolean table of size nxn where n is the length of the given String
2. Set single length palindrome values to true
3. Set palindromes of lenght 2 as true
4. Loop from lengths 3 to n and check palindrome for each length using the following rule
    palindrome[i][j] = true, if palindrome[i+1][j-1] and s[i] == s[j]
5. after the loop, return the longest palindromic substring

Code Snippet

			
package com.ideserve.virendra.questions;

/**
 * <b>IDeserve <br>
 * <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
 * <br><br>
 * Given a String S, find the longest palindromic substring</b><br>
 * <br><br>
 * Example: <br>
 * Input String: <br>
 * "banana"
 * <br>
 * Output: <br>
 * "anana"
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=obBdxeCx_Qs">Longest Palindromic Substring Solution Youtube Link</a> 
 * @author Saurabh
 *
 */
 public class LongestPalindromicSubstring {
	
	public static String LPS(String s) {
		  int n = s.length();
		  int palindromeBeginsAt = 0; //index where the longest palindrome begins
		  int max_len = 1;//length of the longest palindrome
		  boolean palindrome[][] = new boolean[n][n]; //boolean table to store palindrome truth
		  
		  //Trivial case: single letter palindromes
		  for (int i = 0; i < n; i++) {
			  palindrome[i][i] = true;
		  }
		  
		  //Finding palindromes of two characters.
		  for (int i = 0; i < n-1; i++) {
		    if (s.charAt(i) == s.charAt(i+1)) {
		      palindrome[i][i+1] = true;
		      palindromeBeginsAt = i;
		      max_len = 2;
		    }
		  }
		  
		  //Finding palindromes of length 3 to n and saving the longest
		  for (int curr_len = 3; curr_len <= n; curr_len++) {
		    for (int i = 0; i < n-curr_len+1; i++) {
		      int j = i+curr_len-1;
		      if (s.charAt(i) == s.charAt(j) //1. The first and last characters should match 
		    	  && palindrome[i+1][j-1]) //2. Rest of the substring should be a palindrome
		      {
		    	palindrome[i][j] = true; 
		        palindromeBeginsAt = i;
		        max_len = curr_len;
		      }
		    }
		  }
		  return s.substring(palindromeBeginsAt, max_len + palindromeBeginsAt);
		}

	public static void main(String args[])
	{
		System.out.println(LPS("banana"));
	}
}
		

Order of the Algorithm

Time Complexity is O(n^2)
Space Complexity is O(n^2)