How to use Space Optimized method of Dynamic programming to find LPS:- In Data Structures and Algorithms

Using the Tabulation technique of Dynamic programming to find LPS:

In the previous solution you can clearly see that the current row is depending upon previous row. Its mean we are working with only two rows at a time. So, we have created 2 rows and initialized with 0s. We are using vector this time because swapping array becomes easy in vectors. The main logic behind this solution is that we finds the solution of current row then swaps it with the previous one in every iteration until we comes to the end of our strings;

C++

#include <bits/stdc++.h>
using namespace std;

int longestPalinSubseq(string S) {
    string R = S;
    reverse(R.begin(), R.end());
 
    // dp[i][j] will store the length of the longest
    // palindromic subsequence for the substring
    // starting at index i and ending at index j
    vector<int> curr(R.length() + 1, 0);
    vector<int> prev(R.length() + 1, 0);
 
    // Filling up DP table based on conditions discussed
    // in the above approach
    for (int i = 1; i <= S.length(); i++) {
        for (int j = 1; j <= R.length(); j++) {
            if (S[i - 1] == R[j - 1])
                curr[j] = 1 + prev[j - 1];
            else
                curr[j] = max(curr[j - 1], prev[j]);
        }
        prev = curr;
    }
 
    // At the end, DP table will contain the LPS
    // So just return the length of LPS
    return curr[R.length()];
}

// Driver code
int main()
{
    string s = "w3wiki";
    cout << "The length of the LPS is "
         << longestPalinSubseq(s) << endl;

    return 0;
}

Java

import java.util.Arrays;

public class Main {
    public static int longestPalinSubseq(String S) {
        StringBuilder R = new StringBuilder(S);
        R.reverse();

        // dp[i][j] will store the length of the longest
        // palindromic subsequence for the substring
        // starting at index i and ending at index j
        int[] curr = new int[R.length() + 1];
        int[] prev = new int[R.length() + 1];

        // Filling up DP table based on conditions discussed
        // in the above approach
        for (int i = 1; i <= S.length(); i++) {
            for (int j = 1; j <= R.length(); j++) {
                if (S.charAt(i - 1) == R.charAt(j - 1))
                    curr[j] = 1 + prev[j - 1];
                else
                    curr[j] = Math.max(curr[j - 1], prev[j]);
            }
            prev = Arrays.copyOf(curr, curr.length);
        }

        // At the end, DP table will contain the LPS
        // So just return the length of LPS
        return curr[R.length()];
    }

    // Driver code
    public static void main(String[] args) {
        String s = "w3wiki";
        System.out.println("The length of the LPS is " + longestPalinSubseq(s));
    }
}

Python3

def longest_palindrome_subseq(s):
    # Reverse the string
    r = s[::-1]

    # Initialize DP tables
    curr = [0] * (len(r) + 1)
    prev = [0] * (len(r) + 1)

    # Fill DP table
    for i in range(1, len(s) + 1):
        for j in range(1, len(r) + 1):
            if s[i - 1] == r[j - 1]:
                curr[j] = 1 + prev[j - 1]
            else:
                curr[j] = max(curr[j - 1], prev[j])
        prev = curr[:]

    # Return the length of the longest palindromic subsequence
    return curr[-1]

# Driver code
if __name__ == "__main__":
    s = "w3wiki"
    print("The length of the LPS is", longest_palindrome_subseq(s))

JavaScript

// Function to find the length of the longest palindromic subsequence
function longestPalinSubseq(S) {
    let R = S.split('').reverse().join('');

    // dp[i][j] will store the length of the longest
    // palindromic subsequence for the substring
    // starting at index i and ending at index j
    let curr = new Array(R.length + 1).fill(0);
    let prev = new Array(R.length + 1).fill(0);

    // Filling up DP table based on conditions discussed
    // in the above approach
    for (let i = 1; i <= S.length; i++) {
        for (let j = 1; j <= R.length; j++) {
            if (S[i - 1] === R[j - 1]) {
                curr[j] = 1 + prev[j - 1];
            } else {
                curr[j] = Math.max(curr[j - 1], prev[j]);
            }
        }
        prev = [...curr];
    }

    // At the end, DP table will contain the LPS
    // So just return the length of LPS
    return curr[R.length];
}

// Driver code
function main() {
    let s = "w3wiki";
    console.log("The length of the LPS is " + longestPalinSubseq(s));
}

// Calling the main function
main();

Output

The length of the LPS is 5

Time Complexity: O(n²)
Auxiliary Space: O(n)

Longest Palindromic Subsequence (LPS)

Given a string ‘S’, find the length of the Longest Palindromic Subsequence in it.

The Longest Palindromic Subsequence (LPS) is the problem of finding a maximum-length subsequence of a given string that is also a Palindrome.

Longest Palindromic Subsequence

Examples:

Input: S = “w3wiki”
Output: 5
Explanation: The longest palindromic subsequence we can get is of length 5. There are more than 1 palindromic subsequences of length 5, for example: EEKEE, EESEE, EEFEE, …etc.

Input: S = “BBABCBCAB”
Output: 7
Explanation: As “BABCBAB” is the longest palindromic subsequence in it. “BBBBB” and “BBCBB” are also palindromic subsequences of the given sequence, but not the longest ones.

How to use Space Optimized method of Dynamic programming to find LPS:- In Data Structures and Algorithms

Longest Palindromic Subsequence (LPS)

Similar Reads

Contact Us