Java: Longest Palindromic Subsequence

Thought Process

The problem requires finding the length of the longest palindromic subsequence in a given string. A palindromic subsequence reads the same forwards and backwards. We can solve this by leveraging the Longest Common Subsequence (LCS) approach. The idea is to find the LCS between the original string and its reverse. This works because the longest palindromic subsequence is essentially the LCS of the string and its reverse. We use a 2D table to store intermediate results and build the solution incrementally. 

class Solution {
    public int longestPalindromeSubseq(String s) {
        
        StringBuilder sb = new StringBuilder(s);
        String str1 = sb.toString();
        String str2 = sb.reverse().toString();

        int m = str1.length();
        int n = str2.length();

        int[][] t = new int[m+1][n+1];

        for(int i=0;i<=m;i++){
            for(int j=0;j<=n;j++){

                if(i==0 || j==0)
                    t[i][j] = 0;
                else{

                    if(str1.charAt(i-1)==str2.charAt(j-1))
                        t[i][j] = 1 + t[i-1][j-1];
                    else
                        t[i][j] = Math.max(t[i-1][j],t[i][j-1]);
                }
            }
        }
        int lps = t[m][n];
        int i = m;
        int j = n;

        StringBuilder ans = new StringBuilder();
        while(i>0 && j>0){

            if(str1.charAt(i-1) == str2.charAt(j-1)){
                ans.append(str1.charAt(i-1));
                i--;
                j--;
            }
            else {

                if(t[i-1][j]>t[i][j-1])
                    i--;
                else
                    j--;
            }
        }
        // System.out.println(ans.reverse().toString());
        return t[m][n];
    }
}

Code Complexity

Time Complexity: O(n2)

The algorithm iterates through each character of the string and its reverse, resulting in a time complexity of O(n2), where n is the length of the string.

Space Complexity: O(n2)

The algorithm uses a 2D array of size (n+1) x (n+1) to store intermediate results.

Code copied!