{"id":2886,"date":"2023-10-30T19:48:22","date_gmt":"2023-10-30T14:18:22","guid":{"rendered":"https:\/\/www.interviewbit.com\/blog\/?p=2886"},"modified":"2023-10-30T19:48:23","modified_gmt":"2023-10-30T14:18:23","slug":"permutations-of-the-given-string","status":"publish","type":"post","link":"https:\/\/www.interviewbit.com\/blog\/permutations-of-the-given-string\/","title":{"rendered":"Permutation Of String"},"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=\"#approach-backtracking\">Approach: Backtracking<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#c--implementation-for-backtracking-method\">C++ <meta charset=\"utf-8\">Implementation For Backtracking Method<\/a><\/li><li><a href=\"#java--implementation-for-backtracking-method-\">Java <meta charset=\"utf-8\">Implementation For Backtracking Method <\/a><\/li><li><a href=\"#python--implementation-for-backtracking-method-\">Python <meta charset=\"utf-8\">Implementation For Backtracking Method <\/a><\/li><\/ul><li><a href=\"#practice-question\">Practice Question<\/a><\/li><li><a href=\"#faqs\">FAQs<\/a><\/li><ul class=\"gutentoc-toc__list\"><li><a href=\"#q1-how-to-print-a-unique-permutation-of-a-string\">Q.1: How to print a unique permutation of a string?<\/a><\/li><li><a href=\"#q2-what-is-the-approach-used-to-find-permutations-of-a-string\">Q.2: What is the approach used to find permutations of a string?<\/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 a string <strong>S<\/strong>. The task is to print all the possible permutations of the given string.A permutation of a string <strong>S<\/strong> iis another string that contains the same characters, only the order of characters can be different.<br>For example, \u201c<strong>abcd<\/strong>\u201d and \u201c<strong>dabc<\/strong>\u201d are permutations of each other.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img  loading=\"lazy\"  width=\"904\"  height=\"865\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"abcd\"  class=\"wp-image-3172 pk-lazyload\"  data-pk-sizes=\"auto\"  data-ls-sizes=\"(max-width: 904px) 100vw, 904px\"  data-pk-src=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/abcd.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/abcd.png 904w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/abcd-300x287.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/abcd-768x735.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/abcd-380x364.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/abcd-550x526.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/abcd-800x765.png 800w\" ><\/figure>\n\n\n\n<p><strong>Examples: <\/strong><br><strong>Input: <\/strong>S = \u201cabc\u201d<br><strong>Output: <\/strong>[\u201cabc\u201d, \u201cacb\u201d, \u201cbac\u201d, \u201cbca\u201d, \u201ccba\u201d, \u201ccab\u201d]<br><strong>Explanation:<br><\/strong>All the permutations of the given string are given.<\/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=\"approach-backtracking\">Approach: Backtracking<\/h2>\n\n\n\n<p>Using a <strong>backtracking <\/strong>approach, all the permutations of the given string can be printed.<strong><br><\/strong><strong>Backtracking<\/strong> is an algorithm for finding all the possible solutions by exploring all possible ways.<\/p>\n\n\n\n<p>If one of the found solutions turns out to not satisfy the given criteria, it discards the solution and makes some changes and backtracks again.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img  loading=\"lazy\"  width=\"1024\"  height=\"419\"  src=\"data:image\/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAEAAAABAQMAAAAl21bKAAAAA1BMVEUAAP+KeNJXAAAAAXRSTlMAQObYZgAAAAlwSFlzAAAOxAAADsQBlSsOGwAAAApJREFUCNdjYAAAAAIAAeIhvDMAAAAASUVORK5CYII=\"  alt=\"Backtracking\"  class=\"wp-image-3173 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\/Backtracking-1024x419.png\"  data-pk-srcset=\"https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking-1024x419.png 1024w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking-300x123.png 300w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking-768x314.png 768w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking-380x155.png 380w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking-550x225.png 550w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking-800x327.png 800w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking-1160x474.png 1160w, https:\/\/www.interviewbit.com\/blog\/wp-content\/uploads\/2021\/10\/Backtracking.png 1223w\" ><\/figure>\n\n\n\n<p><strong>Algorithm:<\/strong><\/p>\n\n\n\n<ul><li>The backtracking function considers the first index of the given string.<\/li><li>If the index is <strong>N<\/strong>, i.e. length of the string, it means that the current permutation is completed.<\/li><li>Run a loop from current index <strong>idx<\/strong> till <strong>N &#8211; 1<\/strong> and do the following:<ul><li>Swap S[i] and S[idx].<\/li><li>Construct all other possible permutations, from backtrack(idx + 1).<\/li><li>Backtrack again, i.e. swap(S[i], S[idx]).<\/li><\/ul><\/li><\/ul>\n\n\n\n<h3 id=\"c--implementation-for-backtracking-method\"><span id=\"c-implementation-for-backtracking-method\">C++ <meta charset=\"utf-8\">Implementation For Backtracking Method<\/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=\"\">void backtrack(string s, int idx, int N) {\n    if (idx == N)\n      cout &lt;&lt; s &lt;&lt; endl;\n    else {\n      for (int i = idx; i &lt;= N; i++) {\n        swap(s[idx], a[i]);\n        permute(s, idx + 1, N);\n        swap(s[idx], a[i]);\n      }\n    }\n    solve() {\n      string s = \u201dABC\u201d;\n      int N = s.length();\n      backtrack(s, 0, N - 1);\n    }<\/pre>\n\n\n\n<h3 id=\"java--implementation-for-backtracking-method-\"><span id=\"java-implementation-for-backtracking-method\">Java <meta charset=\"utf-8\">Implementation For Backtracking Method <\/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 String swap(String a, int i, int j) {\n  char temp;\n  char[] charArray = a.toCharArray();\n  temp = charArray[i];\n  charArray[i] = charArray[j];\n  charArray[j] = temp;\n  return String.valueOf(charArray);\n}\nprivate void backtrack(String s, int idx, int N) {\n  if (idx == N)\n    System.out.println(s);\n  else {\n    for (int i = idx; i &lt;= N; i++) {\n      s = swap(s, idx, i);\n      backtrack(s, idx + 1, N);\n      s = swap(s, idx, i);\n    }\n  }\n}\nsolve() {\n  String s = \u201dABC\u201d;\n  int N = s.length;\n  backtrack(s, 0, N - 1);\n}<\/pre>\n\n\n\n<h3 id=\"python--implementation-for-backtracking-method-\"><span id=\"python-implementation-for-backtracking-method\">Python <meta charset=\"utf-8\">Implementation For Backtracking Method <\/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 toString(List):\n    return ''.join(List)\n \ndef backtrack(s, idx, N):\n    if idx == N:\n        print(toString(s))\n    else:\n        for i in xrange(idx, N + 1):\n            s[idx], s[i] = s[i], s[idx]\n            backtrack(s, idx + 1, N)\n            s[idx], s[i] = s[i], s[idx]\n \n \ndef solve():\n    a = \"ABC\"\n    N = len(s)\n    s = list(a)\n    permute(s, 0, N - 1)<\/pre>\n\n\n\n<p><strong>Time Complexity:<\/strong> O(N * N!), where N is the length of the string.<br><strong>Space Complexity:<\/strong> O(N!), since one has to keep N! solutions.<\/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<ul><li><a rel=\"noreferrer noopener\" href=\"https:\/\/www.interviewbit.com\/problems\/longest-substring-without-repeat\/\" target=\"_blank\">Longest Substring Without Repeat<\/a><\/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=\"faqs\">FAQs<\/h2>\n\n\n\n<h3 id=\"q1-how-to-print-a-unique-permutation-of-a-string\"><span id=\"q-1-how-to-print-a-unique-permutation-of-a-string\">Q.1: How to print a unique permutation of a string?<\/span><\/h3>\n\n\n\n<p>Ans: To print the unique permutations of the string, put the strings in a HashSet, hence it will give all unique permutations of the strings.<\/p>\n\n\n\n<h3 id=\"q2-what-is-the-approach-used-to-find-permutations-of-a-string\"><span id=\"q-2-what-is-the-approach-used-to-find-permutations-of-a-string\">Q.2: What is the approach used to find permutations of a string?<\/span><\/h3>\n\n\n\n<p><strong>Ans: <\/strong>The backtracking algorithm is to solve this problem.<\/p>\n","protected":false},"excerpt":{"rendered":"Problem Statement Given a string S. The task is to print all the possible permutations of the given&hellip;\n","protected":false},"author":4,"featured_media":3171,"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":[475],"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2886"}],"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\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/comments?post=2886"}],"version-history":[{"count":5,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2886\/revisions"}],"predecessor-version":[{"id":25937,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/posts\/2886\/revisions\/25937"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media\/3171"}],"wp:attachment":[{"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/media?parent=2886"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/categories?post=2886"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.interviewbit.com\/blog\/wp-json\/wp\/v2\/tags?post=2886"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}