C++: 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 originalString) {
        
        // Solution leads to finding the longest common subsequence
        // between a string and its reverse.

        int n = originalString.size();
        string reverseString = originalString;
        reverse(reverseString.begin(),reverseString.end());

        int t[n+1][n+1];
        for(int i=0;i<=n;i++){

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

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

                    if(originalString[i-1]==reverseString[j-1])
                        t[i][j] = 1 + t[i-1][j-1];
                    else
                        t[i][j] = max(t[i-1][j],t[i][j-1]);
                }
            }
        }
        return t[n][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!