How to use Space Optimized method of Dynamic programming to find LPS:- In Data Structures and Algorithms
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;
#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;
}
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));
}
}
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))
// 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(n2)
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.
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.