Solve the problem of finding the Longest Palindromic Subsequence (LPS) using dynamic programming.?

The Longest Palindromic Subsequence (LPS) problem is defined as finding the longest subsequence (not necessarily contiguous) of a given string that is a palindrome.

There are several ways to solve the LPS problem, but we can use dynamic programming to find an efficient solution. The idea is to build a table where each cell (i, j) represents the length of the LPS for the subsequence of the string s starting at i and ending at j. We can fill this table using a bottom-up approach.

Let’s define the function ‘lps(s)‘ that takes a string ‘s‘ as input and returns the length of its LPS. Here’s the dynamic programming algorithm to calculate it:

public int lps(String s) {
    int n = s.length(); // length of the string

    /* Create the table to store the LPS lengths */
    int[][] table = new int[n][n];

    /* Strings of length 1 have LPS of length 1 */
    for (int i = 0; i < n; i++) {
        table[i][i] = 1;
    }

    /* Build the table bottom-up */
    for (int len = 2; len <= n; len++) {
        for (int i = 0; i < n - len + 1; i++) {
            int j = i + len - 1;
            if (s.charAt(i) == s.charAt(j) && len == 2) {
                table[i][j] = 2;
            } else if (s.charAt(i) == s.charAt(j)) {
                table[i][j] = table[i + 1][j - 1] + 2;
            } else {
                table[i][j] = Math.max(table[i + 1][j], table[i][j - 1]);
            }
        }
    }

    /* Return the length of the LPS */
    return table[0][n - 1];
}

Let’s walk through the algorithm step by step and see how it works.

First, we create a 2D array ‘table‘ of size n x n to store the LPS lengths for all substrings. We initialize the diagonal cells (i.e., substrings of length 1) with 1, because any single character is always a palindrome of length 1.

Next, we fill the remaining cells of ‘table‘ iteratively. We start with substrings of length 2 and increment the length of the substring by 1 in each iteration until we reach the whole string. For each substring, we compare the first and last characters. If they are the same, the LPS length is the LPS length of the substring without the first and last characters, plus 2 (because we add the first and last characters to form a longer palindrome). If they are not the same, we take the maximum of the LPS length of the substring without the first character and the LPS length of the substring without the last character.

Finally, we return the LPS length of the whole string, which is stored in ‘table[0][n-1]‘.

Let’s see an example. Suppose we want to find the LPS of the string "ABBDCACB". Here’s how the ‘table‘ would be filled:

   A  B  B  D  C  A  C  B   
A  1  1  1  1  1  1  1  1   
B     1  2  2  2  2  2  3   
B        1  1  1  1  1  1   
D           1  1  1  1  1   
C              1  1  1  1   
A                 1  1  1   
C                    1  1   
B                       1   

The LPS of "ABBDCACB" is "BCACB", which has length 5.

The time complexity of this algorithm is O(n²) because we fill a n x n table. The space complexity is also O(n²) because we use a n x n table to store the LPS lengths. However, we can improve the space complexity to O(n) by using a 1D array instead of a 2D array to store the LPS lengths of the current and previous substrings. This can be achieved by using a "rolling" array technique or by swapping two arrays alternately.