{"id":4290,"date":"2021-11-25T20:42:17","date_gmt":"2021-11-25T15:12:17","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=4290"},"modified":"2021-11-26T10:42:57","modified_gmt":"2021-11-26T05:12:57","slug":"interleaving-strings","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/interleaving-strings\/","title":{"rendered":"Interleaving Strings (C, Java, and Python Code)"},"content":{"rendered":"\n<div class=\"gutentoc tocactive ullist\"><div class=\"gutentoc-toc-wrap\"><div class=\"gutentoc-toc-title-wrap\"><div class=\"gutentoc-toc-title\">Table Of Contents<\/div><div id=\"open\" class=\"text_open\">show<\/div><\/div><div id=\"toclist\"><div class=\"gutentoc-toc__list-wrap\"><ul class=\"gutentoc-toc__list\"><li><a href=\"#approach-1-brute-force\">Approach 1: Brute Force<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c-code\">C++ Code<\/a><\/li><li><a href=\"#java-code\">Java Code<\/a><\/li><li><a href=\"#python-code\">Python Code<\/a><\/li><\/ul><li><a href=\"#faq\">FAQ<\/a><\/li><\/ul><\/div><\/div><\/div><\/div>\n\n\n\n<p>Given three strings <strong>S1, S2<\/strong> and <strong>S3<\/strong>. The task is to check whether the string <strong>S3<\/strong> can be formed by an interleaving of strings <strong>S1<\/strong> and <strong>S2.<br>S3 <\/strong>is said to be interleaving <strong>S1 <\/strong>and <strong>S2<\/strong> if it contains all the characters of <strong>S1<\/strong> and <strong>S2<\/strong> and the order is preserved.<\/p>\n\n\n\n<p><strong>Examples:<\/strong><\/p>\n\n\n\n<p><strong>Input: <br><\/strong>s1 = &#8220;aabcc&#8221;<br>s2 = &#8220;dbbca&#8221;<br>s3 = &#8220;aadbbcbcac&#8221; <strong>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/strong><br><strong>Output:<\/strong> True<br><strong>Explanation:<\/strong><\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"640\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Explanation\"  class=\"wp-image-4435 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\/11\/Explanation-1024x640.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-1024x640.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-300x188.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-768x480.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-1536x960.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-380x238.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-550x344.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-800x500.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation-1160x725.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Explanation.png 1600w\" ><\/figure>\n\n\n\n<p><strong>Input: <\/strong><strong><br><\/strong>s1 = &#8220;aabcc&#8221;<br>s2 = &#8220;dbbca&#8221;<br>s3 = &#8220;aadbbbaccc&#8221;<strong>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<\/strong><\/p>\n\n\n\n<p><strong>Output:<\/strong> False<\/p>\n\n\n\n<h2 id=\"approach-1-brute-force\">Approach 1: Brute Force<\/h2>\n\n\n\n<p>The most basic approach to solve this problem is to simply consider all possible strings of <strong>S1<\/strong> and <strong>S2<\/strong>. If you observe carefully, there are two ways that needs to be taken care of:<\/p>\n\n\n\n<ul><li>If S3[0] == S1[0], move to the next characters and recursively iterate the rest of the string of S1.<\/li><li>If S3[0] == S2[0],&nbsp; move to the next characters and recursively iterate the rest of the string of S2.<\/li><\/ul>\n\n\n\n<p><strong>Algorithm:<\/strong><strong><br><\/strong><\/p>\n\n\n\n<ul><li>The base case of the recursive function is when the strings <strong>S1, S2 <\/strong>and <strong>S3<\/strong> are empty.<\/li><li>For the rest of the function, check whether <strong>S3[0] == S1[0]<\/strong>, then recursively traverse for <strong>S1[1&#8230;N]<\/strong>.&nbsp;<\/li><li>Similarly, if <strong>S3[0] == S2[0]<\/strong>, then recursively traverse for <strong>S2[1&#8230;N].<\/strong><\/li><\/ul>\n\n\n\n<p id=\"-implementation-of-the-approach-\"><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\"><span id=\"c-code-2\">C++ Code<\/span><\/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=\"\">bool isInterleaving(string X, string Y, string S) {\n  if (!X.length() &amp;amp;&amp;amp; !Y.length() &amp;amp;&amp;amp; !S.length()) {\n    return true;\n  }\n \n  if (!S.length()) {\n    return false;\n  }\n \n  if (X.length() &amp;amp;&amp;amp; S[0] == X[0]) {\n    return isInterleaving(X.substr(1), Y, S.substr(1));\n  }\n \n  if (Y.length() &amp;amp;&amp;amp; S[0] == Y[0]) {\n    return isInterleaving(X, Y.substr(1), S.substr(1));\n  }\n \n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"java-code\"><span id=\"java-code-2\">Java Code<\/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 boolean isInterleaving(String X, String Y, String S) {\n  if (X.length() == 0 &amp;amp;&amp;amp; Y.length() == 0 &amp;amp;&amp;amp; S.length() == 0) {\n    return true;\n  }\n \n  if (S.length() == 0) {\n    return false;\n  }\n \n  if (X.length() != 0 &amp;amp;&amp;amp; S.charAt(0) == X.charAt(0)) {\n    return isInterleaving(X.substring(1), Y, S.substring(1));\n  }\n \n  if (Y.length() != 0 &amp;amp;&amp;amp; S.charAt(0) == Y.charAt(0)) {\n    return isInterleaving(X, Y.substring(1), S.substring(1));\n  }\n \n  return false;\n}<\/pre>\n\n\n\n<h3 id=\"python-code\"><span id=\"python-code-2\">Python Code<\/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 isInterleaving(X, Y, S):\n    if not X and not Y and not S:\n        return True\n \n    if not S:\n        return False\n \n    if X and S[0] == X[0]:\n        return isInterleaving(X[1:], Y, S[1:])\n \n    if Y and S[0] == Y[0]:\n        return isInterleaving(X, Y[1:], S[1:])\n \n    return False<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(2^(N+M)), where N and M is the length of the string S1 and S2.<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N + M), for the recursive stack.<\/p>\n\n\n\n<h2 id=\"approach-2-dynamic-programming\">Approach 2: Dynamic Programming<\/h2>\n\n\n\n<p>In the previous approach, if you observe carefully, there were many overlapping subproblems which we were calculating again and again.<\/p>\n\n\n\n<p>For example :<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"640\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Dynamic Programming\"  class=\"wp-image-4436 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\/11\/Dynamic-Programming-1024x640.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-1024x640.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-300x188.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-768x480.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-1536x960.png 1536w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-380x238.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-550x344.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-800x500.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming-1160x725.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Dynamic-Programming.png 1600w\" ><\/figure>\n\n\n\n<p>To avoid repetitive calculations, the idea is to use <strong>Dynamic Programming <\/strong>to solve the problem. The DP table is built as follows. Consider the following example:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"1274\"  height=\"737\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"\"  class=\"wp-image-4463 pk-lazyload\"  data-pk-sizes=\"auto\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/11\/Example-1.gif\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>Create a <strong>2D<\/strong> <strong>dp <\/strong>array of size <strong>N X M<\/strong>, where N is the size of S1<strong> <\/strong>and M is the size of S2.<\/li><li>Run a nested loop from i = 0 till i = N+1 and j = 0 till j =&nbsp; M + 1 and fill the table as follows:<ul><li>If i == 0 and j == 0:<ul><li>Dp[i][j] = True<\/li><\/ul><\/li><li>Else if i == 0 and S2[j &#8211; 1] == S3[i + j &#8211; 1]:<ul><li>Dp[i][j] = dp[i][j &#8211; 1] + 1<\/li><\/ul><\/li><li>Else if j == 0 and S1[j &#8211; 1] == S3[i + j &#8211; 1]:<ul><li>Dp[i][j] = dp[i &#8211; 1][j] + 1<\/li><\/ul><\/li><li>Else:<ul><li>(DP[i-1][j] and S1[i-1] == S3[i+j-1] ) or (DP[i][j-1] and S2[j-1] == S3[i+j-1] )<\/li><\/ul><\/li><\/ul><\/li><li>Return dp[N][M]<\/li><\/ul>\n\n\n\n<p id=\"-implementation-of-the-approach-\"><strong>Implementation of the Approach:<\/strong><\/p>\n\n\n\n<h3 id=\"c-code\">C++ Code<\/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=\"\">bool isInterleaving(string X, string Y, string S) {\n  int M = X.size();\n  int N = Y.size();\n \n  if (M + N != S.size()) {\n    return false;\n  }\n \n  bool T[M + 1][N + 1];\n \n  for (int i = 0; i &amp;lt;= M; i++) {\n    for (int j = 0; j &amp;lt;= N; j++) {\n      if (i == 0 &amp;amp;&amp;amp; j == 0) {\n        T[i][j] = true;\n      } else if (i and j and X[i - 1] == S[i + j - 1] and Y[j - 1] == S[i + j - 1]) {\n        T[i][j] = T[i - 1][j] || T[i][j - 1];\n      } else if (i and X[i - 1] == S[i + j - 1]) {\n        T[i][j] = T[i - 1][j];\n      } else if (j and Y[j - 1] == S[i + j - 1]) {\n        T[i][j] = T[i][j - 1];\n      }\n    }\n  }\n  return T[M][N];\n}<\/pre>\n\n\n\n<h3 id=\"java-code\">Java Code<\/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 boolean isInterleaving(String X, String Y, String S) {\n  int M = X.length();\n  int N = Y.length();\n  if (M + N != S.length()) {\n    return false;\n  }\n  boolean[][] T = new boolean[M + 1][N + 1];\n  for (int i = 0; i &amp;lt;= M; i++) {\n    for (int j = 0; j &amp;lt;= N; j++) {\n      if (i == 0 &amp;amp;&amp;amp; j == 0) {\n        T[i][j] = true;\n      } else if (i != 0 &amp;amp;&amp;amp; j != 0 &amp;amp;&amp;amp; X.charAt(i - 1) == S.charAt(i + j - 1) &amp;amp;&amp;amp;\n        Y.charAt(j - 1) == S.charAt(i + j - 1)) {\n        T[i][j] = T[i - 1][j] || T[i][j - 1];\n      } else if (i != 0 &amp;amp;&amp;amp; X.charAt(i - 1) == S.charAt(i + j - 1)) {\n        T[i][j] = T[i - 1][j];\n      } else if (j != 0 &amp;amp;&amp;amp; Y.charAt(j - 1) == S.charAt(i + j - 1)) {\n        T[i][j] = T[i][j - 1];\n      }\n    }\n  }\n  return T[M][N];\n}<\/pre>\n\n\n\n<h3 id=\"python-code\">Python Code<\/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 isInterleaving(X, Y, S):\n    M, N = len(X), len(Y)\n    if M + N != len(S):\n        return False\n \n    T = [[False for x in range(N + 1)] for y in range(M + 1)]\n \n    for i in range(0, M + 1):\n        for j in range(0, N + 1):\n \n            if i == 0 and j == 0:\n                T[i][j] = True\n \n            elif i and j and X[i - 1] == S[i + j - 1] and Y[j - 1] == S[i + j - 1]:\n                T[i][j] = T[i - 1][j] or T[i][j - 1]\n \n            elif i and X[i - 1] == S[i + j - 1]:\n                T[i][j] = T[i - 1][j]\n \n            elif j and Y[j - 1] == S[i + j - 1]:\n                T[i][j] = T[i][j - 1]\n \n    return T[M][N]<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N*M), where N and M is the length of the string S1 and S2.<\/p>\n\n\n\n<p><strong>Space Complexity:<\/strong> O(N * M), since dp array is used.<\/p>\n\n\n\n<p id=\"-practice-questions-\"><strong>Practice Questions:<\/strong><\/p>\n\n\n\n<p><a href=\"https:\/\/www.interviewbit.com\/problems\/interleaving-strings\/\" target=\"_blank\" rel=\"noreferrer noopener\">Interleaving Strings<\/a><\/p>\n\n\n\n<h2 id=\"faq\">FAQ<\/h2>\n\n\n\n<ul><li><strong>What are the two types of possibilities for interleaving?<\/strong><strong><br><\/strong>The two types of possibilities are as follows:<ol><li>If S3[0] == S1[0], move to the next characters and recursively iterate the rest of the string of S1.<\/li><\/ol><\/li><\/ul>\n\n\n\n<p>If S3[0] == S2[0],&nbsp; move to the next characters and recursively iterate the rest of the string of S2.<strong><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"Given three strings S1, S2 and S3. The task is to check whether the string S3 can be&hellip;\n","protected":false},"author":5,"featured_media":4437,"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":[611],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4290"}],"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=4290"}],"version-history":[{"count":12,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4290\/revisions"}],"predecessor-version":[{"id":4464,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/4290\/revisions\/4464"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/4437"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=4290"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=4290"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=4290"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}