{"id":2415,"date":"2023-06-12T17:07:28","date_gmt":"2023-06-12T11:37:28","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2415"},"modified":"2023-06-12T17:13:36","modified_gmt":"2023-06-12T11:43:36","slug":"longest-common-subsequence","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/longest-common-subsequence\/","title":{"rendered":"Longest Common Subsequence"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\" 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=\"#1-simple-approach-solution\">1. Simple Approach Solution<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#printing-longest-common-subsequence\">Printing Longest Common Subsequence<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation\">C++ Implementation<\/a><\/li><li><a href=\"#java-implementation\">Java Implementation<\/a><\/li><li><a href=\"#python-implementation\">Python Implementation<\/a><\/li><li><a href=\"#recursive-tree-for-example-1\">Recursive Tree for Example 1<\/a><\/li><\/ul><\/ul><li><a href=\"#2-dynamic-programming-approach\">2. Dynamic Programming Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#implementation-of-the-dp-approach\">Implementation of the DP Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-dp-approach\">C++ Implementation of DP Approach<\/a><\/li><li><a href=\"#java-implementation-of-dp-approach\">Java Implementation of DP Approach<\/a><\/li><\/ul><\/ul><li><a href=\"#3-bottom-up-technique\">3. Bottom-Up Technique<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#implementation\">Implementation<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-implementation-of-bottom-up-technique\">C++ Implementation of Bottom-Up Technique<\/a><\/li><li><a href=\"#java-implementation-of-bottom-up-technique\">Java Implementation of Bottom-Up Technique<\/a><\/li><li><a href=\"#-python-implementation-of-bottom-up-technique\"><meta charset=\"utf-8\">Python Implementation of Bottom-Up Technique<\/a><\/li><\/ul><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#frequently-asked-questions\">Frequently Asked Questions<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-do-you-find-the-longest-common-subsequence\">Q.1: How do you find the longest common subsequence?<\/a><\/li><li><a href=\"#q2-what-is-the-time-complexity-of-the-longest-common-subsequence\">Q.2: What is the time complexity of the longest common subsequence?<\/a><\/li><li><a href=\"#q3-is-the-longest-common-subsequence-np-complete\">Q.3: Is the longest common subsequence NP-complete?<\/a><\/li><\/ul><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<h2 id=\"problem-statement\">Problem Statement<\/h2>\n\n\n\n<p>Given two strings, the task is to find the longest common subsequence present in the given strings in the same order.<\/p>\n\n\n\n<p><strong>The subsequence<\/strong> of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"393\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LCS\"  class=\"wp-image-2453 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\/LCS.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-300x115.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-768x295.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-380x146.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-550x211.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-800x307.jpg 800w\" ><\/figure><\/div>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<ul><li><strong>Input s1:<\/strong> &#8220;abcde&#8221;<\/li><li><strong>s2:<\/strong> &#8220;ace&#8221;<\/li><li><strong>Output:<\/strong> 3<\/li><\/ul>\n\n\n\n<p><em><strong>Explanation:<\/strong> Subsequence \u201cace\u201d of length 3 is the longest.<\/em><\/p>\n\n\n\n<ul><li><strong>Input s1:<\/strong> &#8220;ezupkr&#8221;<\/li><li><strong>s2:<\/strong> &#8220;ubmrapg&#8221;<\/li><li><strong>Output:<\/strong> 2<\/li><\/ul>\n\n\n\n<p><em><strong>Explanation:<\/strong> Subsequence \u201cur\u201d of length 2 is the longest.<\/em><\/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=\"1-simple-approach-solution\">1. Simple Approach Solution<\/h2>\n\n\n\n<p>The simple approach checks for every subsequence of sequence 1 whether it is also a subsequence in sequence 2.<\/p>\n\n\n\n<p>Sequence S1 and S2 with length n and m respectively. So, the lcs of S1 and S2 is the maximum of LCS( S1[1\u2026m-1],S2[1\u2026.n]),LCS(S1[1\u2026m],S2[1\u2026..n-1])).<\/p>\n\n\n\n<ul><li>So, the parameters needed are the two sequences and two iterators (S1, S2,i,j) for the sequences<\/li><li>The base case will be if any of the lengths is not valid (i.e less or equal to zero) then return<\/li><li>Check for the current element of both iterators if equal then include that in LCS and make a recursive call for the prev element in both sequences (i.e. i-1,j-1).<\/li><li>If both iterator elements are not equal then LCS can be obtained by including any of the current elements. So making both calls and taking the maximum of those<ul><li>Including S1\u2019s recursive call will be LCS(S1,S2,i,j-1) [ i is for S1 and j is for S2]<\/li><li>Including S2\u2019s recursive call will be LCS(S1,S2,i-1,j)<\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"printing-longest-common-subsequence\">Printing Longest Common Subsequence<\/h3>\n\n\n\n<h4 id=\"c-implementation\">C++ Implementation<\/h4>\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=\"\">\/\/ Finding Length of longest common subsequence\n\/\/ iterating from last character so i and j are the length of strings initially\nint LCS(string X, string Y, int i, int j) {\n  if (i == 0 || j == 0) {\n    return 0;\n  }\n\n  if (X[m - 1] == Y[n - 1]) {\n    return LCS(X, Y, i - 1, j - 1) + 1;\n  }\n\n  return max(LCS(X, Y, i, j - 1), LCS(X, Y, i - 1, j));\n}<\/pre>\n\n\n\n<h4 id=\"java-implementation\">Java Implementation<\/h4>\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 static int LCS(String X, String Y, int i, int j) {\n  if (i == 0 || j == 0) {\n    return 0;\n  }\n\n  if (X.charAt(i - 1) == Y.charAt(j - 1)) {\n    return LCS(X, Y, i - 1, j - 1) + 1;\n  }\n\n  return Integer.max(LCS(X, Y, i, j - 1),\n    LCS(X, Y, i - 1, j));\n}<\/pre>\n\n\n\n<h4 id=\"python-implementation\">Python Implementation<\/h4>\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=\"\"># sequences `S1[0...m-1]` and `Y[0...n-1]`\ndef LCS(X, Y, m, n):\n \n    # return if the end of either sequence is reached\n    if m == 0 or n == 0:\n        return 0\n \n    if X[i - 1] == Y[j - 1]:\n        return LCS(X, Y, i - 1, j - 1) + 1\n \n    return max(LCS(X, Y, i, j - 1), LCS(X, Y, i- 1, j))<\/pre>\n\n\n\n<h4 id=\"recursive-tree-for-example-1\">Recursive Tree for Example 1<\/h4>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"941\"  height=\"1024\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Recursive Tree for Example\"  class=\"wp-image-2455 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 941px) 100vw, 941px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example-941x1024.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example-941x1024.jpg 941w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example-276x300.jpg 276w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example-768x836.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example-380x413.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example-550x598.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example-800x870.jpg 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Recursive-Tree-for-Example.jpg 1024w\" ><figcaption>Recursive Tree for Example<\/figcaption><\/figure>\n\n\n\n<p>So total subsequence possible is 2^n for a sequence of length n<\/p>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(2^(n+m)), Where n and m are lengths of sequences.<\/li><li><strong>Space complexity:<\/strong> O(1)<\/li><\/ul>\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=\"2-dynamic-programming-approach\">2. Dynamic Programming Approach<\/h2>\n\n\n\n<ul><li>We can see in our recursive tree that many of the sub-problems are overlapping and it would be very much increased as the tree size increases and it would compute for the same problem again.<\/li><li>Using <a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\"><strong>dynamic programming<\/strong><\/a> we can compute a problem and store the optimal result and use it further avoiding repeated execution.<\/li><li>DP[i][j] state: longest sequence using starting I characters of string S1 and starting j characters of string S2.<\/li><\/ul>\n\n\n\n<h3 id=\"implementation-of-the-dp-approach\">Implementation of the DP Approach<\/h3>\n\n\n\n<h4 id=\"c-implementation-of-dp-approach\">C++ Implementation of DP Approach<\/h4>\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=\"\">\/\/ dp[][] Initialized with -1\nint dp[N][M];\nint LCS(string X, string Y, int i, int j) {\n  if (i == 0 || j == 0) {\n    return 0;\n  }\n  \/\/ Here we are checking if this problem has been computed earlier \n  if (dp[i][j] != -1)\n    return dp[i][j];\n  if (X[m - 1] == Y[n - 1]) {\n    return dp[i][j] = LCS(X, Y, i - 1, j - 1) + 1;\n  }\n  \/\/ computing and storing the problem in dp\n  return dp[i][j] = max(LCS(X, Y, i, j - 1), LCS(X, Y, i - 1, j));\n}<\/pre>\n\n\n\n<h4 id=\"java-implementation-of-dp-approach\">Java Implementation of DP Approach<\/h4>\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 static int LCS(String X, String Y, int i, int j, Map &lt; String, Integer > dp) {\n  if (i == 0 || j == 0) {\n    return 0;\n  }\n  String key = i + \"|\" + j;\n  if (!dp.containsKey(key)) {\n    if (X.charAt(i - 1) == Y.charAt(j - 1)) {\n      dp.put(key, LCS(X, Y, i - 1, j - 1, dp) + 1);\n    } else\n      dp.put(key, Integer.max(LCS(X, Y, i, j - 1, dp),\n        LCS(X, Y, i - 1, j, dp)));\n  }\n  return dp.get(key);\n}<\/pre>\n\n\n\n<p>Python Implementation of DP Approach<\/p>\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 LCSLength(X, Y, i, j, dp={}):\n\n    if i == 0 or j == 0:\n        return 0\n    key = (i, j)\n    if key not in dp:\n\n        if X[i - 1] == Y[j - 1]:\n            dp[key] = LCSLength(X, Y, i - 1, j - 1, dp) + 1\n\n        else:\n            dp[key] = max(LCSLength(X, Y, i, j - 1, dp), LCSLength(X, Y, i - 1, j, dp))\n\n    return dp[key]<\/pre>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(nm), Where n and m are the lengths of sequences.<\/li><li><strong>Space complexity:<\/strong> O(nm)<\/li><\/ul>\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=\"3-bottom-up-technique\">3. Bottom-Up Technique<\/h2>\n\n\n\n<p>It\u2019s a bottom-up technique in which we compute the smaller values of the problem and compute larger ones from them. It\u2019s more efficient w.r.t time complexity as it doesn\u2019t use the recursive stack and is hence more efficient.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"313\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"LCS Iterative Approach\"  class=\"wp-image-2452 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\/LCS-Iterative-Approach.jpg\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-Iterative-Approach.jpg 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-Iterative-Approach-300x92.jpg 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-Iterative-Approach-768x235.jpg 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-Iterative-Approach-380x116.jpg 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-Iterative-Approach-550x168.jpg 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/LCS-Iterative-Approach-800x245.jpg 800w\" ><figcaption>LCS Iterative Approach<\/figcaption><\/figure>\n\n\n\n<h3 id=\"implementation\">Implementation<\/h3>\n\n\n\n<h4 id=\"c-implementation-of-bottom-up-technique\">C++ Implementation of Bottom-Up Technique<\/h4>\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 LCS(string a, string b) {\n    int m = a.length(), n = b.length();\n    vector&lt;vector&lt;int>> dp(m + 1, vector&lt;int>(n + 1, 0));\n    for (int i = 1; i &lt;= m; i++) {\n        for (int j = 1; j &lt;= n; j++) {\n            if (a[i - 1] == b[j - 1])\n                dp[i][j] = dp[i - 1][j - 1] + 1;\n            else {\n                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);\n            }\n        }\n    }\n    return dp[m][n];\n}\n<\/pre>\n\n\n\n<h4 id=\"java-implementation-of-bottom-up-technique\">Java Implementation of Bottom-Up Technique<\/h4>\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 LCS_iterative(String X, String Y) {\n  int dp[][] = new int[Y.length() + 1][X.length() + 1];\n  char[] s1 = X.toCharArray();\n  char[] s2 = Y.toCharArray();\n\n  for (int i = 1; i &lt;= s2.length; i++) {\n    for (int j = 1; j &lt;= s1.length; j++) {\n      if (s2[i - 1] == s1[j - 1]) {\n        dp[i][j] = 1 + dp[i - 1][j - 1];\n      } else {\n        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);\n      }\n    }\n  }\n  return dp[s2.length][s1.length];\n}<\/pre>\n\n\n\n<h4 id=\"-python-implementation-of-bottom-up-technique\"><span id=\"python-implementation-of-bottom-up-technique\"><meta charset=\"utf-8\">Python Implementation of Bottom-Up Technique<\/span><\/h4>\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 solve(self, X, Y):\n    # Initializing X dp array of size\n    n = len(X)\n    m = len(Y)\n    dp = [[0 for i in range(m + 1)] for i in range(n + 1)]\n\n    for i in range(n - 1, -1, -1):\n        for j in range(m - 1, -1, -1):\n            if X[i] == Y[j]:\n                dp[i][j] = dp[i + 1][j + 1] + 1\n            else:\n                dp[i][j] = max(dp[i + 1][j], dp[i][j + 1])\n    return dp[0][0]<\/pre>\n\n\n\n<ul><li><strong>Time complexity:<\/strong> O(nm), Where n and m are the lengths of sequences.<\/li><li><strong>Space complexity:<\/strong> O(nm)<\/li><\/ul>\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-common-subsequence\/\" target=\"_blank\" rel=\"noreferrer noopener\">Longest Common Subsequency<\/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<h3 id=\"q1-how-do-you-find-the-longest-common-subsequence\"><span id=\"q-1-how-do-you-find-the-longest-common-subsequence\">Q.1: How do you find the longest common subsequence?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The most efficient method is to use the dynamic programming approach of storing sub-problems.<\/p>\n\n\n\n<h3 id=\"q2-what-is-the-time-complexity-of-the-longest-common-subsequence\"><span id=\"q-2-what-is-the-time-complexity-of-the-longest-common-subsequence\">Q.2: What is the time complexity of the longest common subsequence?<\/span><\/h3>\n\n\n\n<p><strong>Ans:<\/strong> It depends if we don\u2019t use dynamic programming to store subproblems then it would be O(2^(n+m)) time and O(1) space and using dynamic programming its O(n<em>m) time and O(n<\/em>m) space where n,m are lengths of sequence.<\/p>\n\n\n\n<h3 id=\"q3-is-the-longest-common-subsequence-np-complete\"><span id=\"q-3-is-the-longest-common-subsequence-np-complete\">Q.3: Is the longest common subsequence NP-complete?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The 2D-LCS problem is NP-hard.<\/p>\n\n\n\n<p><strong>Proof:<\/strong> We prove the hardness of the problem by a reduction from the Clique problem.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given two strings, the task is to find the longest common subsequence present in the given&hellip;\n","protected":false},"author":5,"featured_media":2454,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_daextam_enable_autolinks":"1","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":[399,404],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2415"}],"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=2415"}],"version-history":[{"count":15,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2415\/revisions"}],"predecessor-version":[{"id":20042,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2415\/revisions\/20042"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2454"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2415"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2415"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2415"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}