Longest Palindromic Subsequence

Given a string S, find the longest palindromic subsequence.


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 DP table of size nxn where n is the length of the given String
2. Set single length palindrome values to 1
3. Loop from lengths 2 to n and check palindrome for each length using the following rule
    palindrome[i][j] = palindrome[i+1][j-1] + 2, if s[i] == s[j]
    palindrome[i][j] = Math.max(palindrome[i+1][j], palindrome[i][j-1]), if s[i] != s[j]
4. after the loop, return palindrome[0][n-1]


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>
 * Longest Palindromic Subsequence - Dynamic Programming Solution</b><br>
 * Given a string  S, find the longest palindromic subsequence
 * <br><br>
 * Example: <br>
 * Input String: <br>
 * "LPSSAPAL"
 * <br>
 * Output: <br>
 * "LPSPL"
 * <br><br>
 * <a href="https://www.youtube.com/watch?v=U4yPae3GEO0">Longest Palindromic Subsequence Solution Youtube Link</a> 
 * @author Virendra
 *
 *
 */
 
 public class LongestPalindromicSubsequence {
	
	public static int LPS(String s) {
		  int n = s.length();
		  int palindrome[][] = new int[n][n]; //Table to store lengths of palindrome subsequences.
		  
		  //Trivial case: single letter palindromes
		  for (int i = 0; i < n; i++) {
			  palindrome[i][i] = 1;
		  }
		  
		  //Finding palindromes of length 2 to n and saving the longest
		  for (int curr_len = 2; 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))//Trim if match and add 2  
		      {
		    	palindrome[i][j] = palindrome[i+1][j-1] + 2; 
		      }
		      else //Trim one at a time and take max
		      {
		        palindrome[i][j] = Math.max(palindrome[i+1][j], palindrome[i][j-1]);
		      }
		    }
		  }
		  
		  return palindrome[0][n-1];
		}

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

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