{"id":731,"date":"2023-12-05T18:27:07","date_gmt":"2023-12-05T18:27:07","guid":{"rendered":"https:\/\/favtutor.com\/articles\/?p=731"},"modified":"2023-12-06T09:36:26","modified_gmt":"2023-12-06T09:36:26","slug":"longest-palindromic-subsequence","status":"publish","type":"post","link":"https:\/\/favtutor.com\/articles\/longest-palindromic-subsequence\/","title":{"rendered":"Longest Palindromic Subsequence (C++, Java, Python)"},"content":{"rendered":"\n<p>In string manipulation and pattern recognition, one of the famous problems is finding the Longest Palindromic Subsequence within a given string. As we know, a palindromic subsequence is a sequence of characters that reads the same forwards and backward. In this article, we will understand this problem and discuss an optimal approach using dynamic programming to solve this problem.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Longest Palindromic Subsequence Problem<\/strong><\/h2>\n\n\n\n<p>In this LPS problem, we are given a string S and we have to find the length of the Longest Palindromic Subsequence. <strong>The Longest Palindromic Subsequence refers to the maximum-length subsequence of the string that is also a palindrome.<\/strong><\/p>\n\n\n\n<p>A subsequence is a sequence of characters obtained from the original sequence and their order is preserved, but not necessarily all characters need to be included. <\/p>\n\n\n\n<p>Let us understand this problem with an example:<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\">String = \u201cfavtutor\u201d<br>Output = 3<\/p>\n\n\n\n<p>One possible longest palindromic subsequence is &#8220;tut&#8221;. As we can see if we read it backward it\u2019s the same.<\/p>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"253\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-1-1024x253.png\" alt=\"Example of Longest palindromic subsequence\" class=\"wp-image-736\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-1-1024x253.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-1-300x74.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-1-768x190.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-1-750x185.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-1-1140x282.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/1-1.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<h2 class=\"wp-block-heading\"><strong>Dynamic Programming to Find LPS<\/strong><\/h2>\n\n\n\n<p>The longest sequence of letters reads the same backward as forward. Now, if you reverse the entire original string, the longest palindromic subsequence will still be a palindrome (reads the same backward and forward), and its length will stay the same. It&#8217;s like a property that these palindromic things maintain even when we reverse it.<\/p>\n\n\n\n<p class=\"has-black-color has-text-color has-background\" style=\"background-color:#fedcba\">String = \u201cfavtutor\u201d<br>Reversed_string = \u201crotutvaf\u201d<\/p>\n\n\n\n<p><strong>Steps to solve using DP:<\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Create a dp (<a href=\"https:\/\/favtutor.com\/blogs\/dynamic-programming\">dynamic programming<\/a>) array of size [n][m], where n and m are the lengths of String and reversed_string, respectively. This array will store the result of every subproblem until it does not occur again.<\/li>\n\n\n\n<li>We will initialize the dp array with -1 because none of the subproblems is solved in the beginning.<\/li>\n\n\n\n<li>we will find the answer for particular indices (e.g., LCS (ind1, ind2)), and if s1[i] == s2[j] we will do i = i-1, j = j-1. Otherwise we will try (i,j-1) or (i-1,j).<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"303\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1024x303.png\" alt=\"Steps to solve LPS using Dynamic Programming\" class=\"wp-image-737\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1024x303.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-300x89.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-768x228.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-750x222.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1-1140x338.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/2-1.png 1279w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>string[i]==reversed_string[j] is equal in case of \u201ctut\u201d.<\/li>\n<\/ul>\n\n\n<div class=\"wp-block-image\">\n<figure class=\"aligncenter size-large\"><img decoding=\"async\" width=\"1024\" height=\"163\" src=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-1024x163.png\" alt=\"result of the example\" class=\"wp-image-739\" srcset=\"https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-1024x163.png 1024w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-300x48.png 300w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-768x122.png 768w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-750x120.png 750w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1-1140x182.png 1140w, https:\/\/favtutor.com\/articles\/wp-content\/uploads\/2023\/12\/3-1.png 1280w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n<\/div>\n\n\n<ul class=\"wp-block-list\">\n<li>We first check whether the answer has already been calculated using the dp array (i.e., dp[ind1][ind2] != -1). If it has, we simply return the value from the dp[ind1][ind2].<\/li>\n\n\n\n<li>If the answer has not been calculated yet, we will use the recursive relation as usual. However, before returning from the function, we set dp[ind1][ind2] to the solution we obtained.<\/li>\n<\/ul>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>C++ Code<\/strong><\/h3>\n\n\n\n<p>Here is the C++ program to solve the LPS problem using dynamic programming:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-c++src&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;C++&quot;,&quot;modeName&quot;:&quot;cpp&quot;}\">#include &lt;iostream&gt;\n#include &lt;vector&gt;\n#include &lt;algorithm&gt;\n\nusing namespace std;\n\nint longestPalindromeSubseqHelper(string &amp;s, string &amp;t, int i, int j, vector&lt;vector&lt;int&gt;&gt; &amp;dp) {\n    \/\/ Base case: if the substring has one or zero characters, it's a palindrome\n    if (i &gt;= s.length() || j &gt;= t.length()) {\n        return 0;\n    }\n\n    \/\/ Check if the result is already computed\n    if (dp[i][j] != -1) {\n        return dp[i][j];\n    }\n\n    \/\/ If the characters at the current positions match, extend the palindrome\n    if (s[i] == t[j]) {\n        dp[i][j] = 1 + longestPalindromeSubseqHelper(s, t, i + 1, j + 1, dp);\n    } else {\n        \/\/ If the characters don't match, take the maximum of excluding either\n        \/\/ the last character from the beginning or the last character from the end\n        dp[i][j] = max(longestPalindromeSubseqHelper(s, t, i + 1, j, dp),\n                       longestPalindromeSubseqHelper(s, t, i, j + 1, dp));\n    }\n\n    return dp[i][j];\n}\n\nint longestPalindromeSubseq(string s) {\n    \/\/ Create a reversed copy of the input string\n    string t = s;\n    reverse(t.begin(), t.end());\n\n    \/\/ Create a 2D array for dynamic programming and initialize with -1\n    vector&lt;vector&lt;int&gt;&gt; dp(s.length(), vector&lt;int&gt;(t.length(), -1));\n\n    \/\/ Call the helper function to compute the result\n    return longestPalindromeSubseqHelper(s, t, 0, 0, dp);\n}\n\nint main() {\n    string s = &quot;favtutor&quot;;\n    int result = longestPalindromeSubseq(s);\n\n    cout &lt;&lt; &quot;The length of the longest palindromic subsequence in '&quot; &lt;&lt; s &lt;&lt; &quot;' is: &quot; &lt;&lt; result &lt;&lt; endl;\n\n    return 0;\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Java Code<\/strong><\/h3>\n\n\n\n<p>You can also implement it in Java as well:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;clike&quot;,&quot;mime&quot;:&quot;text\/x-java&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Java&quot;,&quot;modeName&quot;:&quot;java&quot;}\">import java.util.Arrays;\n\npublic class LongestPalindromicSubsequence {\n\n    static int longestPalindromeSubseqHelper(String s, String t, int i, int j, int[][] dp) {\n        \/\/ Base case: if the substring has one or zero characters, it's a palindrome\n        if (i &gt;= s.length() || j &gt;= t.length()) {\n            return 0;\n        }\n\n        \/\/ Check if the result is already computed\n        if (dp[i][j] != -1) {\n            return dp[i][j];\n        }\n\n        \/\/ If the characters at the current positions match, extend the palindrome\n        if (s.charAt(i) == t.charAt(j)) {\n            dp[i][j] = 1 + longestPalindromeSubseqHelper(s, t, i + 1, j + 1, dp);\n        } else {\n            \/\/ If the characters don't match, take the maximum of excluding either\n            \/\/ the last character from the beginning or the last character from the end\n            dp[i][j] = Math.max(longestPalindromeSubseqHelper(s, t, i + 1, j, dp),\n                                longestPalindromeSubseqHelper(s, t, i, j + 1, dp));\n        }\n\n        return dp[i][j];\n    }\n\n    static int longestPalindromeSubseq(String s) {\n        \/\/ Create a reversed copy of the input string\n        StringBuilder reversed = new StringBuilder(s).reverse();\n        String t = reversed.toString();\n\n        \/\/ Create a 2D array for dynamic programming and initialize with -1\n        int[][] dp = new int[s.length()][t.length()];\n        for (int[] row : dp) {\n            Arrays.fill(row, -1);\n        }\n\n        \/\/ Call the helper function to compute the result\n        return longestPalindromeSubseqHelper(s, t, 0, 0, dp);\n    }\n\n    public static void main(String[] args) {\n        String s = &quot;favtutor&quot;;\n        int result = longestPalindromeSubseq(s);\n        System.out.println(&quot;The length of the longest palindromic subsequence in '&quot; + s + &quot;' is: &quot; + result);\n    }\n}<\/pre><\/div>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Python Code<\/strong><\/h3>\n\n\n\n<p>Below is the Python program for this approach:<\/p>\n\n\n\n<div class=\"wp-block-codemirror-blocks-code-block code-block\"><pre class=\"CodeMirror\" data-setting=\"{&quot;mode&quot;:&quot;python&quot;,&quot;mime&quot;:&quot;text\/x-python&quot;,&quot;theme&quot;:&quot;material&quot;,&quot;lineNumbers&quot;:true,&quot;styleActiveLine&quot;:false,&quot;lineWrapping&quot;:false,&quot;readOnly&quot;:true,&quot;language&quot;:&quot;Python&quot;,&quot;modeName&quot;:&quot;python&quot;}\">def longestPalindromeSubseqHelper(s, t, i, j, dp):\n    # Base case: if the substring has one or zero characters, it's a palindrome\n    if i &gt;= len(s) or j &gt;= len(t):\n        return 0\n\n    # Check if the result is already computed\n    if dp[i][j] != -1:\n        return dp[i][j]\n\n    # If the characters at the current positions match, extend the palindrome\n    if s[i] == t[j]:\n        dp[i][j] = 1 + longestPalindromeSubseqHelper(s, t, i + 1, j + 1, dp)\n    else:\n        # If the characters don't match, take the maximum of excluding either\n        # the last character from the beginning or the last character from the end\n        dp[i][j] = max(longestPalindromeSubseqHelper(s, t, i + 1, j, dp),\n                       longestPalindromeSubseqHelper(s, t, i, j + 1, dp))\n\n    return dp[i][j]\n\ndef longestPalindromeSubseq(s):\n    # Create a reversed copy of the input string\n    t = s[::-1]\n\n    # Create a 2D array for dynamic programming and initialize with -1\n    dp = [[-1 for _ in range(len(t))] for _ in range(len(s))]\n\n    # Call the helper function to compute the result\n    return longestPalindromeSubseqHelper(s, t, 0, 0, dp)\n\n# Main function\ns = &quot;favtutor&quot;\nresult = longestPalindromeSubseq(s)\nprint(f&quot;The length of the longest palindromic subsequence in '{s}' is: {result}&quot;)<\/pre><\/div>\n\n\n\n<p><strong>Output:<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-black-color has-text-color has-background\" style=\"background-color:#fedcba\"><code>The length of the longest palindromic subsequence in 'favtutor' is: 3<\/code><\/pre>\n\n\n\n<h3 class=\"wp-block-heading\"><strong>Complexity Analysis<\/strong><\/h3>\n\n\n\n<p>The time complexity is determined by the number of subproblems that need to be solved. In this case, there are O(m*n) subproblems, where m is the length of the first string (s1) and\u00a0n is the length of the reversed_string.<\/p>\n\n\n\n<p>The space complexity is determined by the memory required for the memoization table (dp). The table is a 2D array of size (m+1)*(n+1), where m is the length of s1 and n is the length of reversed_string. So overall space complexity is O(m*n).<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Conclusion<\/strong><\/h2>\n\n\n\n<p>This article explores the Longest palindromic Subsequence (LPS) problem, which involves finding the length of the longest palindromic subsequence in a string. Using the intuition that the <a href=\"https:\/\/favtutor.com\/articles\/longest-common-subsequence\/\" data-type=\"link\" data-id=\"https:\/\/favtutor.com\/articles\/longest-common-subsequence\/\">longest common subsequence<\/a> between a string and its reversed_string is the longest palindromic subsequence, we can easily solve this problem using dynamic programming. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Learn how to find the longest palindromic subsequence using dynamic programming with implementation in C++, Java, and Python.<\/p>\n","protected":false},"author":12,"featured_media":733,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"jnews-multi-image_gallery":[],"jnews_single_post":null,"jnews_primary_category":{"id":"","hide":""},"footnotes":""},"categories":[7],"tags":[25,15],"class_list":["post-731","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures-algorithms","tag-dp","tag-leetcode"],"_links":{"self":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/731","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/users\/12"}],"replies":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/comments?post=731"}],"version-history":[{"count":6,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/731\/revisions"}],"predecessor-version":[{"id":830,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/posts\/731\/revisions\/830"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media\/733"}],"wp:attachment":[{"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/media?parent=731"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/categories?post=731"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/favtutor.com\/articles\/wp-json\/wp\/v2\/tags?post=731"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}