Longest Palindromic Substring

Given a string S, find the longest palindromic substring.


Please try solving this problem before jumping on the solution

Click to learn






Subscribe for more updates



Preparing for interviews? IDeserve team is here to help.




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


Hone your coding skills!




AngryNerds Practice platform »

Algorithm Visualization




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)


Contribution

  • Sincere thanks from IDeserve community to Virendra Karappa for compiling current post.

    Virendra Karappa

    Ninja Programmer