{"id":2642,"date":"2023-06-27T20:03:54","date_gmt":"2023-06-27T14:33:54","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2642"},"modified":"2023-06-27T20:03:55","modified_gmt":"2023-06-27T14:33:55","slug":"longest-common-substring","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/longest-common-substring\/","title":{"rendered":"Longest Common Substring"},"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=\"#simple-approach\">Simple Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code-of-simple-approach\">C++ Code of Simple Approach<\/a><\/li><li><a href=\"#-java-code-of-simple-approach\"><meta charset=\"utf-8\">Java Code of Simple Approach<\/a><\/li><li><a href=\"#-python-code-of-simple-approach\"><meta charset=\"utf-8\">Python Code of Simple Approach<\/a><\/li><\/ul><li><a href=\"#recursive-approach\">Recursive Approach<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#longest-common-substring-c\">Longest Common Substring C++<\/a><\/li><li><a href=\"#-longest-common-substring-java\"><meta charset=\"utf-8\">Longest Common Substring Java<\/a><\/li><li><a href=\"#-longest-common-substring-python\"><meta charset=\"utf-8\">Longest Common Substring Python<\/a><\/li><\/ul><li><a href=\"#dynamic-programming-appraoch\">Dynamic Programming Appraoch<\/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=\"#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-substring\">Q.1: How do you find the longest common substring?<\/a><\/li><li><a href=\"#q2-what-is-the-time-complexity-of-the-longest-common-substring\">Q.2: What is the time complexity of the longest common substring?<\/a><\/li><li><a href=\"#q3-what-is-the-time-complexity-of-finding-the-longest-non-repeated-substring\">Q.3: What is the time complexity of finding the longest non-repeated substring?<\/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 substring present in the given strings in the same order.<\/p>\n\n\n\n<p>The substring is a contiguous sequence of characters within a string. For example, \u201cbit\u201d is a substring of the string \u201cInterviewbit\u201d.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"500\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Common Substring\"  class=\"wp-image-2725 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\/Common-Substring.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Common-Substring.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Common-Substring-300x146.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Common-Substring-768x375.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Common-Substring-380x186.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Common-Substring-550x269.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Common-Substring-800x391.png 800w\" ><\/figure><\/div>\n\n\n\n<p><strong>Example:<\/strong><\/p>\n\n\n\n<p><strong>Input s1:<\/strong> &#8220;dadef&#8221;<br><strong>s2:<\/strong> &#8220;adwce&#8221;<br><strong>Output:<\/strong> 2<br><strong>Explanation:<\/strong> Substring \u201cad\u201d of length 2 is the longest.<\/p>\n\n\n\n<p><strong>Input s1:<\/strong> &#8220;abcdxyz&#8221;<br><strong>s2:<\/strong> &#8220;xyzabcd&#8221;<br><strong>Output:<\/strong> 4<br><strong>Explanation:<\/strong> Substring \u201cabcd\u201d of length 4 is the longest.<\/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=\"simple-approach\">Simple Approach<\/h2>\n\n\n\n<p>The simple approach checks for every substring of sequence 1 whether it is also a substring in sequence 2.<\/p>\n\n\n\n<p>Sequence S1 and S2 with length n and m respectively<\/p>\n\n\n\n<ul><li>Find all the substrings of sequence 1 in O(n^2)<\/li><li>Iterate through sequence 2 and check whether the current substring is a substring of this string in O(m)<\/li><li>Maximize the length of all the common substrings.<\/li><\/ul>\n\n\n\n<h3 id=\"c-code-of-simple-approach\">C++ Code of Simple 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=\"\">void lcsubstr(string str1,string str2)\n{\n      int ans = 0;\n\n\tfor (int i = 0; i &lt; str1.length(); i++) \n\t{\n         for (int j = 0; j &lt; str2.length(); j++) {\n\t\tint k = 0;\n\t\twhile ((i + k) &lt; str1.length() &amp;&amp; (j + k) &lt; str2.length() \n\t\t\t\t&amp;&amp; str1[i + k] == str2[j + k]) \n\t\t{\n\t\t\tk = k + 1;\n\t\t}\n\n\t\tans = max(ans, k);\n\t   }\n\t}\n      return ans;\n}<\/pre>\n\n\n\n<h3 id=\"-java-code-of-simple-approach\"><span id=\"java-code-of-simple-approach\"><meta charset=\"utf-8\">Java Code of Simple 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 static int lcsubstr(string str1, string str2){\n\tint ans = 0;\n\n\tfor (int i = 0; i &lt; str1.length(); i++) \n\t{\n         for (int j = 0; j &lt; str2.length(); j++) {\n\t\tint k = 0;\n\t\twhile ((i + k) &lt; str1.length() &amp;&amp; (j + k) &lt; str2.length() \n\t\t\t\t&amp;&amp; str1.charAt(i + k) == str2.charAt(j + k)) \n\t\t{\n\t\t\tk = k + 1;\n\t\t}\n\n\t\tans = Math.max(ans, k);\n\t   }\n\t}\n      return ans;\n  }<\/pre>\n\n\n\n<h3 id=\"-python-code-of-simple-approach\"><span id=\"python-code-of-simple-approach\"><meta charset=\"utf-8\">Python Code of Simple 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 lcsubstr(str1, str2):\n    \tans = 0;\n\n\tfor i in range(len(str1)):\n         for j in range(len(str2)):\n\t\tk = 0;\n\t\twhile ((i + k) &lt; len(str1) and (j + k) &lt; len(str2) \n\t\t\t\tand str1[i + k] == str2[j + k]): \n\t\t\tk = k + 1;\n\n\t\tans = max(ans, k);\n      return ans;<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(n^2 * m), Where n and m are the lengths of sequences.<br><strong>Space complexity:<\/strong> O(1)<\/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=\"recursive-approach\">Recursive Approach<\/h2>\n\n\n\n<p>In the recursive approach, the idea is to recursively match characters of both the sequences and maximize in case the characters are the same.<\/p>\n\n\n\n<p><strong>Algorithm<\/strong><\/p>\n\n\n\n<ul><li>Initialise a variable <strong>res<\/strong>, to count the longest common substring.<\/li><li>Let <strong>i<\/strong> and <strong>j<\/strong> be the index of the <strong>str1<\/strong> and <strong>str2<\/strong> pointing to the last character of both the strings.<\/li><li>If both the characters are the same, i.e. <strong>str1[i] == str2[j]<\/strong>, increment the value of <strong>res<\/strong> by <strong>1.<\/strong><\/li><li>Proceed to match the remaining characters, by decrementing the pointers <strong>i <\/strong>and <strong>j<\/strong> each time the characters don&#8217;t match.<\/li><li>Maximize the value of <strong>count<\/strong> for every step.<\/li><li>Repeat the above process, until we reach the starting of both strings.<\/li><\/ul>\n\n\n\n<h3 id=\"longest-common-substring-c\">Longest Common Substring C++<\/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 solve(int i, int j, int count, string str1, string str2)\n    {\n \n        if (i == 0 || j == 0)\n        {\n            return count;\n        }\n \n        if (str1[i - 1] == str2[j - 1])\n        {\n            count = solve(i - 1, j - 1, count + 1, str1, str2);\n        }\n        int count1 = solve(i, j - 1, 0, str1, str2);\n\n        int count2 = solve(i - 1, j, 0, str1, str2);\n\n        count = max({count, count1,count2});\n        return count;\n    }\n    void lcsubstr(){\n        int ans = solve(N, M, 0, str1, str2);\n        return ans;\n    }<\/pre>\n\n\n\n<h3 id=\"-longest-common-substring-java\"><span id=\"longest-common-substring-java\"><meta charset=\"utf-8\">Longest Common Substring Java<\/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 solve(int i, int j, int count)\n    {\n \n        if (i == 0 || j == 0)\n        {\n            return count;\n        }\n \n        if (str1.charAt(i - 1) == str2.charAt(j - 1))\n        {\n            count = solve(i - 1, j - 1, count + 1, str1, str2);\n        }\n\n        int count1 = solve(i, j - 1, 0, str1, str2);\n\n        int count2 = solve(i - 1, j, 0, str1, str2);\n\n        count = Math.max(count,Math.max(count1,count2));\n\n        return count;\n    }\n    static int lcsubstr(){\n        int ans = solve(N, M, 0, str1, str2);\n        return ans;\n    }<\/pre>\n\n\n\n<h3 id=\"-longest-common-substring-python\"><span id=\"longest-common-substring-python\"><meta charset=\"utf-8\">Longest Common Substring Python<\/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 solve(i, j, count, str1, str2):\n        if i == 0 or j == 0:\n            return count;\n \n        if str1[i - 1] == str2[j - 1]:\n            count = solve(i - 1, j - 1, count + 1, str1, str2);\n\n        count1 = solve(i, j - 1, 0);\n\n        count2 = lcs(i - 1, j, 0);\n\n        count = max({count, count1,count2});\n        return count;\ndef lcsubstr():\n     ans = solve(N, M, 0, str1, str2);\n     return ans;<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(3 ^(n*m)), where n and m are the lengths of sequences.<br><strong>Space complexity:<\/strong> O(max(n, m))<\/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=\"dynamic-programming-appraoch\">Dynamic Programming Appraoch<\/h2>\n\n\n\n<p>The longest common substring can be efficiently calculated using the <a href=\"https:\/\/www.interviewbit.com\/courses\/programming\/dynamic-programming\/\" target=\"_blank\" rel=\"noreferrer noopener\"><strong>dynamic programming<\/strong><\/a> approach.<\/p>\n\n\n\n<p>The idea is to calculate the longest common suffix for all substrings of both sequences.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"786\"  height=\"305\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Longest Common Substring DP Approach\"  class=\"wp-image-2727 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 786px) 100vw, 786px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Common-Substring-DP-Approach.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Common-Substring-DP-Approach.png 786w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Common-Substring-DP-Approach-300x116.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Common-Substring-DP-Approach-768x298.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Common-Substring-DP-Approach-380x147.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Longest-Common-Substring-DP-Approach-550x213.png 550w\" ><\/figure><\/div>\n\n\n\n<p>Consider the below example &#8211;<br><strong>str1<\/strong> = \u201cABCXYZAY\u201d<br><strong>str2<\/strong> =\u201d \u201cXYZABCB\u201d<\/p>\n\n\n\n<p>The longest common substring is <strong>\u201cXYZA\u201d,<\/strong> which is of length 4.<\/p>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-full\"><img  loading=\"lazy\"  width=\"1024\"  height=\"574\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Length of a Substring\"  class=\"wp-image-2726 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\/Length-of-a-Substring.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Length-of-a-Substring.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Length-of-a-Substring-300x168.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Length-of-a-Substring-768x431.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Length-of-a-Substring-380x213.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Length-of-a-Substring-550x308.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Length-of-a-Substring-800x448.png 800w\" ><\/figure><\/div>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Create a <strong>dp<\/strong> array of size <strong>N * M<\/strong>, where <strong>N<\/strong> and <strong>M <\/strong>denote the length of the sequences.<\/li><li>Iterate over the string <strong>str1 <\/strong>and <strong>str2<\/strong> using a nested loop.<\/li><li>The below conditions follows:<ul><li>If <strong>i == 0 or j == 0, dp[i][j] = 0<\/strong><\/li><li>If <strong>str1[i] == str2[j]<\/strong>, <strong>dp[i][j] = 1 + dp[i &#8211; 1][j &#8211; 1]<\/strong><\/li><\/ul><\/li><li>Keep a track of the maximum value obtained so far.<\/li><li>Return the <strong>maximum<\/strong> value.<\/li><\/ul>\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 LCSubStr(string str1, string str2, int N, int M)\n{\n    int LCSuff[N + 1][M + 1];\n    int mx = 0;    \n    for (int i = 0; i &lt;= N; i++)\n    {\n        for (int j = 0; j &lt;= M; j++)\n        {\n              if (i == 0 || j == 0){\n                LCSuff[i][j] = 0;\n              }\n \n            else if (str1[i - 1] == str2[j - 1]) {\n                LCSuff[i][j] = LCSuff[i - 1][j - 1] + 1;\n                mx = max(mx, LCSuff[i][j]);\n            }\n            else\n                LCSuff[i][j] = 0;\n        }\n    }\n    return mx;\n}<\/pre>\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 LCSubStr(char str1[], char str2[], int N, int M){\n        int LCStuff[][] = new int[N + 1][M + 1];\n       \n        int mx = 0;\n\n        for (int i = 0; i &lt;= N; i++)\n        {\n            for (int j = 0; j &lt;= M; j++)\n            {\n                if (i == 0 || j == 0)\n                    LCStuff[i][j] = 0;\n                else if (str1[i - 1] == str2[j - 1])\n                {\n                    LCStuff[i][j]\n                        = LCStuff[i - 1][j - 1] + 1;\n                    mx = Integer.max(mx,\n                                         LCStuff[i][j]);\n                }\n                else\n                    LCStuff[i][j] = 0;\n            }\n        }\n        return mx;\n    }<\/pre>\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 LCSubStr(str1, str2, N, M):\n \n    LCSuff = [[0 for k in range(M+1)] for l in range(N+1)]\n    mx = 0\n    for i in range(N + 1):\n        for j in range(M + 1):\n            if (i == 0 or j == 0):\n                LCSuff[i][j] = 0\n            elif (str1[i-1] == str2[j-1]):\n                LCSuff[i][j] = LCSuff[i-1][j-1] + 1\n                mx = max(result, LCSuff[i][j])\n            else:\n                LCSuff[i][j] = 0\n    return mx<\/pre>\n\n\n\n<p><strong>Time complexity:<\/strong> O(n*m), Where n and m are the lengths of sequences.<br><strong>Space complexity:<\/strong> O(n*m)<\/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-common-prefix\/\" target=\"_blank\" rel=\"noreferrer noopener\">Longest Common Prefix<\/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-substring\"><span id=\"q-1-how-do-you-find-the-longest-common-substring\">Q.1: How do you find the longest common substring?<\/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-substring\"><span id=\"q-2-what-is-the-time-complexity-of-the-longest-common-substring\">Q.2: What is the time complexity of the longest common substring?<\/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(3^(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-what-is-the-time-complexity-of-finding-the-longest-non-repeated-substring\"><span id=\"q-3-what-is-the-time-complexity-of-finding-the-longest-non-repeated-substring\">Q.3: What is the time complexity of finding the longest non-repeated substring?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The time complexity of finding the longest non-repeated substring is O(n).<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given two strings, the task is to find the longest common substring present in the given&hellip;\n","protected":false},"author":5,"featured_media":2728,"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,451],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2642"}],"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=2642"}],"version-history":[{"count":4,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2642\/revisions"}],"predecessor-version":[{"id":20929,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2642\/revisions\/20929"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/2728"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2642"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2642"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2642"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}