{"id":2676,"date":"2021-10-14T12:10:00","date_gmt":"2021-10-14T06:40:00","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2676"},"modified":"2021-10-21T11:50:08","modified_gmt":"2021-10-21T06:20:08","slug":"longest-palindromic-subsequence","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/longest-palindromic-subsequence\/","title":{"rendered":"Longest Palindromic Subsequence (With Solution)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive nostyle\" style=\"max-width:400px\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"toggletwo\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#problem-statement\">Problem Statement<\/a><\/li><li><a href=\"#brute-force-recursion-approach\">Brute force: Recursion Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#-java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/a><\/li><li><a href=\"#-python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/a><\/li><\/ul><li><a href=\"#efficient-approach-using-dynamic-programming\">Efficient Approach (Using Dynamic Programming)<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-for-dp-approach\">C++ Code for DP Approach<\/a><\/li><li><a href=\"#-java-code-for-dp-approach\"><meta charset=\"utf-8\">Java Code for DP Approach<\/a><\/li><li><a href=\"#-python-code-for-dp-approach\"><meta charset=\"utf-8\">Python Code for DP Approach<\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given a string <strong>S<\/strong>, find the common palindromic sequence ( A sequence that does not need to be contiguous and is a palindrome), which is common in itself.<\/p>\n\n\n\n<p>You need to return the length of the longest palindromic subsequence in A.<\/p>\n\n\n\n<p>A string is said to be palindrome if the reverse of the string is the same as the string. For example, \u201cabba\u201d is a palindrome, but \u201cabbc\u201d is not a palindrome.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <\/strong>S = \u201cBEBEEED\u201d<br><strong>Output: <\/strong>4<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<p>The longest common palindromic subsequence is &#8220;EEEE&#8221;, which has a length of 4<br><br><strong>Input: <\/strong>S = \u201cAABCDEBAZ\u201d<br><strong>Output:<\/strong> 5<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"299\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LPS Example\"  class=\"wp-image-2759 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-4.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-4.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-4-300x88.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-4-768x224.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-4-380x111.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-4-550x161.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-4-800x234.png 800w\" ><\/figure>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"brute-force-recursion-approach\">Brute force: Recursion Approach<\/h2>\n\n\n\n<p>A simple approach to solve this problem is to generate all the subsequences of the given string and find the longest palindromic string among all the generated strings. There are a total of 2^N strings possible, where N denotes the length of the given string.<\/p>\n\n\n\n<p>The idea is to check and compare the first and last characters of the string. There are only <strong>two<\/strong> possibilities for the same:<\/p>\n\n\n\n<ul><li>If the first and the last characters are the same, it can be ensured that both the characters can be considered in the final palindrome and hence, add <strong>2<\/strong> to the result, since we have found a sequence of length <strong>2<\/strong> and recurse the remaining substring <strong>S[i + 1, j &#8211; 1]<\/strong>.<\/li><li>In case, the first and the last characters aren\u2019t the same, the following operation must be performed:<ul><li>Recurse <strong>S[i + 1, j]<\/strong><\/li><li>Recurse <strong>S[ i, j&nbsp; &#8211; 1]<\/strong><\/li><\/ul><\/li><li>Find the maximum length obtained amongst them.<\/li><\/ul>\n\n\n\n<p>The recursion tree can be shown as follows: <strong>LPS(1, N) <\/strong>denotes the length of the longest palindromic subsequence of the given string <strong>S[1..N].<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"443\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LPS Brute force Approach\"  class=\"wp-image-2755 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-1.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-1.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-1-300x130.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-1-768x332.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-1-380x164.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-1-550x238.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-1-800x346.png 800w\" ><figcaption>LPS Brute force Approach<\/figcaption><\/figure>\n\n\n\n<h3 id=\"c-implementation\">C++ Implementation<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">int LPS(string S, int left, int right){\n        if (left > right) {\n            return 0;\n        } \n        if(left == right){\n            return 1;\n        }   \n        if (S[left] == S[right])\n        {\n            return 2 + LPS(str,left+1,right-1);\n        }\n  \n  \n     return max(LPS(S, left, right - 1), LPS(S, left + 1, right));\n    }<\/pre>\n\n\n\n<p>Practice on our\u00a0<a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/online-cpp-compiler\/\" target=\"_blank\">C++ Compiler<\/a><\/p>\n\n\n\n<h3 id=\"-java-implementation\"><span id=\"java-implementation\"><meta charset=\"utf-8\">Java Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\"> static int LPS(String S, int left, int right){\n        if (left > right) {\n            return 0;\n        } \n        if(left == right){\n            return 1;\n        }   \n        if (S.charAt(left) == S.charAt(right) )\n        {\n            return 2 + LPS(str,left+1,right-1);\n        }\n  \n  \n     return Math.max(LPS(S, left, right - 1), LPS(S, left + 1, right));\n    }<\/pre>\n\n\n\n<p>Practice on our\u00a0<a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/online-java-compiler\/\" target=\"_blank\">Java Compiler<\/a><\/p>\n\n\n\n<h3 id=\"-python-implementation\"><span id=\"python-implementation\"><meta charset=\"utf-8\">Python Implementation<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def LPS(S, left, right){\n        if left > right:\n            return 0\n        If left == right:\n            return 1\n        \n        if S[left] == S[right]:\n            return 2 + LPS(str,left+1,right-1);\n  \n  \n       return max(LPS(S, left, right - 1), LPS(S, left + 1, right))<\/pre>\n\n\n\n<p>Practice on our\u00a0<a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/online-python-compiler\/\" target=\"_blank\">Python Compiler<\/a><\/p>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(2^N) where N is the size of the string <strong>S<\/strong>.<br><strong>Space Complexity:<\/strong> O(1), as no extra space is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"efficient-approach-using-dynamic-programming\">Efficient Approach (Using Dynamic Programming)<\/h2>\n\n\n\n<p>The efficient approach uses a dynamic programming approach for the problem.<\/p>\n\n\n\n<p><br>It can be clearly observed that some of the subsequences are repeating i.e it contains <strong>overlapping subproblems<\/strong>.&nbsp;Let us take the example of the string <strong>ABCDE<\/strong>.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"749\"  height=\"733\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LPS DP Approach\"  class=\"wp-image-2761 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 749px) 100vw, 749px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-6.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-6.png 749w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-6-300x294.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-6-380x372.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-6-550x538.png 550w\" ><figcaption>LPS DP Approach<\/figcaption><\/figure><\/div>\n\n\n\n<p>The subproblems <strong>BCD <\/strong>is repeating twice, hence instead of calculating the value twice, we can instead store it in a table. Let\u2019s illustrate the algorithm with the string &#8211; <strong>\u201caxbdba\u201d<\/strong>.<br><br>Consider a <strong>dp <\/strong>array of size <strong>N * N<\/strong>.<br><\/p>\n\n\n\n<p><strong>Algorithm: <\/strong><\/p>\n\n\n\n<p>Fill the table with a start case, <strong>dp[i, i] == 1<\/strong>, since all single char in a string is a palindrome, which length is 1.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"921\"  height=\"315\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LPS DP Step 1\"  class=\"wp-image-2763 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 921px) 100vw, 921px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-8.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-8.png 921w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-8-300x103.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-8-768x263.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-8-380x130.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-8-550x188.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-8-800x274.png 800w\" ><\/figure>\n\n\n\n<p>When s[i] == s[j]\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"443\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LPS DP S2\"  class=\"wp-image-2757 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-2.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-2.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-2-300x130.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-2-768x332.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-2-380x164.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-2-550x238.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-2-800x346.png 800w\" ><\/figure>\n\n\n\n<p>When s[i] == s[j]\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"458\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LPS DP S3\"  class=\"wp-image-2760 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-5.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-5.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-5-300x134.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-5-768x344.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-5-380x170.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-5-550x246.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-5-800x358.png 800w\" ><\/figure>\n\n\n\n<p>Continue the process until the whole dp array is filled.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"423\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LPS DP S4\"  class=\"wp-image-2762 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 1024px) 100vw, 1024px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-7.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-7.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-7-300x124.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-7-768x317.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-7-380x157.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-7-550x227.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Panlindromic-Subsequence-Image-7-800x330.png 800w\" ><\/figure>\n\n\n\n<p>Return <strong>dp[0][N&nbsp; &#8211; 1] <\/strong>is the <strong>longest palindromic subsequence(LPS)<\/strong><\/p>\n\n\n\n<h3 id=\"c-code-for-dp-approach\">C++ Code for DP Approach<\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"cpp\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int LPS(string S) {\n        int dp[S.length()][S.length()];\n        \n        for (int i = S.length() - 1; i >= 0; i--) {\n            dp[i][i] = 1;\n            for (int j = i+1; j &lt; S.length(); j++) {\n                if (S[i] == S[j]) {\n                    dp[i][j] = dp[i+1][j-1] + 2;\n                } else {\n                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);\n                }\n            }\n        }\n        return dp[0][S.length()-1];\n }<\/pre>\n\n\n\n<h3 id=\"-java-code-for-dp-approach\"><span id=\"java-code-for-dp-approach\"><meta charset=\"utf-8\">Java Code for DP Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"java\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">public int LPS(String S) {\n        int[][] dp = new int[S.length()][S.length()];\n        \n        for (int i = S.length() - 1; i >= 0; i--) {\n            dp[i][i] = 1;\n            for (int j = i+1; j &lt; S.length(); j++) {\n                if (S.charAt(i) == S.charAt(j)) {\n                    dp[i][j] = dp[i+1][j-1] + 2;\n                } else {\n                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);\n                }\n            }\n        }\n        return dp[0][S.length()-1];\n }<\/pre>\n\n\n\n<h3 id=\"-python-code-for-dp-approach\"><span id=\"python-code-for-dp-approach\"><meta charset=\"utf-8\">Python Code for DP Approach<\/span><\/h3>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">def LPS(S):\n        dp = [[0 for x in range(len(S))] for x in range(len(S))]\n        \n        for i in range(len(S) - 1, -1, -1):\n            dp[i][i] = 1;\n            for j in range(i + 1, len(S)):\n                if S[i] == S[j]:\n                    dp[i][j] = dp[i+1][j-1] + 2;\n                 \n                else:\n                    dp[i][j] = max(dp[i+1][j], dp[i][j-1]);\n                \n            \n        return dp[0][S.length()-1];<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N^2) where N is the size of the string <strong>S<\/strong>.<br><strong>Space Complexity:<\/strong> O(N^2), as extra <strong>dp<\/strong> array is used.<\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"practice-question\">Practice Question<\/h2>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/longest-palindromic-subsequence\/\" target=\"_blank\" rel=\"noreferrer noopener\">Longest Palindromic Subsequence<\/a><\/p>\n\n\n\n<hr class=\"wp-block-separator has-text-color has-background has-black-background-color has-black-color is-style-wide\"\/>\n\n\n\n<h2 id=\"frequently-asked-questions\">Frequently Asked Questions<\/h2>\n\n\n\n<p><strong>How to find the longest palindromic subsequence?<br><\/strong>The <strong>LPS <\/strong>can be calculated efficiently using the dynamic programming approach, which can be solved in O(N^2), where N is the size of the given string.<br><\/p>\n\n\n\n<p><strong>How to find the palindromic subsequence from the table?<\/strong><strong><br><\/strong>To find the subsequence, which gives us the longest <strong>LPS<\/strong>, backtrack from <strong>dp[0][N &#8211; 1]<\/strong> and trace the path back to <strong>dp[0][0].<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a string S, find the common palindromic sequence ( A sequence that does not need&hellip;\n","protected":false},"author":5,"featured_media":2754,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"","csco_singular_sidebar":"","csco_page_header_type":"","csco_appearance_grid":"","csco_page_load_nextpost":"","csco_post_video_location":[],"csco_post_video_location_hash":"","csco_post_video_url":"","csco_post_video_bg_start_time":0,"csco_post_video_bg_end_time":0},"categories":[145],"tags":[457,399,461],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2676"}],"collection":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2676"}],"version-history":[{"count":3,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2676\/revisions"}],"predecessor-version":[{"id":2864,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2676\/revisions\/2864"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2754"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2676"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2676"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2676"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}