How To Permute A String - Generate All Permutations Of A String

Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe....
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Question: Given a string, print all permutations of the string and return an array of them. No duplicates are allowed.
Whenever we work with problems like this, the fact that it is a string and that it is an array are interchangeable. We will permute an array the same way that we permute a string.
Why is this a backtracking problem? Because we are placing an item and then exploring all possibilities from there.
Whenever we have a problem that says "generate" or "compute" and it is an expression of several decision points that comprise a larger possibility set...WE HAVE BACKTRACKING.
The 3 Keys To Backtracking
Our Choice
What character we place in a "slot"
Our Constraints
None really...but at each decision point we will have fewer characters to work with because of our previous decisions.
Our Goal
Let n be the string length. Place n characters.
Complexities
Time: O(n * n!)
There are n! permutations and it takes O(n) time to add each one to our result array
Space: O(n)
We are not returning an array here so linear space because our recursion will go at maximum n elements deep since we make n choices of placement at maximum
If we did store and return an array our space complexity would be O(n * n!) since we would have n! permutations and each permutation would be of length n. If we consider the returned array of all permutation strings as NOT part of space, the call stack dominates space. We are back to O(n).
++++++++++++++++++++++++++++++++++++++++++++++++++
HackerRank: / @hackerrankofficial
Tuschar Roy: / tusharroy2525
GeeksForGeeks: / @geeksforgeeksvideos
Jarvis Johnson: / vsympathyv
Success In Tech: / @successintech
++++++++++++++++++++++++++++++++++++++++++++++++++
This question is number 16.3 in the fantastic book "Elements of Programming Interviews" by Adnan Aziz

[@BackToBackSWE]

Table of Contents: (I'm sorry, I messed up the audio and am talking pretty loud) Problem Introduction 0:00 - 1:57 The "3 Keys To Backtracking" 1:57 - 4:55 The FULL Recursion Walkthrough For "boat" 4:55 - 22:57 Time & Space Complexities 22:57 - 27:53 Wrap Up / Conclusion 27:53 - 28:18 This is super long because of the walkthrough...I'm sorry. Here is a good example of the code: javarevisited.blogspot.com/2015/08/how-to-find-all-permutations-of-string-java-example.html (If this link doesn't work then you can find the code anywhere, just know the concepts and you can implement it however you want, but I really should have walked through that code snippet. I will try to this in a later video, this is my fault.)

[@jaseharold3119]

pro trick: you can watch series at flixzone. Me and my gf have been using them for watching lots of of movies lately.

[@samirmanuel8944]

@Jase Harold Yea, been using flixzone} for since december myself =)

[@optimizedpran1247]

I want to get "No More Decisions To Make Backtrack" tattooed on my arm after this.

[@BackToBackSWE]

hahaha same

[@akn4336]

Write a code to count number of “now”s in this video! 😂 Just kidding, good tutorial

[@BackToBackSWE]

I say that a lot. Weird mannerism. I can't control them....well I could consciously try...eh...whatever

[@AlexBonillas]

Time complexity for that proposed "and now"-count Algorithm is the same as this permutations Algorithm.... also kidding of course, this is a good tutorial

[@ElGalloUltimo]

11:51 "I feel like a robot right now" :) But you are not a robot, so it is exhausting for a human being to do this. It's amazing how much simpler the actual code is than doing it manually yourself. It is one of the most powerful examples of why computers are useful. Despite all that, I *really* appreciate you putting yourself through that on video because it fully and completely demonstrates the intuition behind the code.

[@BackToBackSWE]

sure thx

[@yangyu4489]

love the ENERGY my guy - earned a sub

[@BackToBackSWE]

thx

[@vishalcelestine8654]

Not the teacher we deserve, but the teacher we need..hats off !!!

[@BackToBackSWE]

thanks haha

[@LeafNBlade]

Amazing explanation, I have a interview coming up and i will keep this in mind for any permutation problem!

[@BackToBackSWE]

love

[@faisalsal1]

Jeez, I thought he is going to write a code :(

[@BackToBackSWE]

Here Is My Response: backtobackswe.com/im-sorry Github: github.com/bephrem1/backtobackswe/issues/1

[@NB19273]

Amazing explanation very clear! I did a masters (1 year conversion course) in Computer Science and they never even mentioned the concept of backtracking so this is very helpful thanks.

[@BackToBackSWE]

sure

[@sushmithasnataraj5122]

Who else feels that this channel deserves more subscribers?

[@BackToBackSWE]

It does alright. The growth rate is good. It can be faster and we haven't gone on to create "viral" content. Since November I've been mostly coding and not focused on growing the channel. Between December 2018 and November 2019 I only made niche programming question videos and they operate like a library. A library is stable and grows slowly. The channel still operates like a library and not an active mechanism of rich media generation. If we made media that could scale to capture more people (less technical, talk about salaries or something which is a hot, attractive topic) we would grow exponentially. I am well aware where we stand and what the KZbin is as well as where it can go. Entities on the internet can deserve things, but attention distribution is not fair and follows the pattern of natural selection with a great bit of unfairness.

[@sushmithasnataraj5122]

@@BackToBackSWE I love the content on this channel. Do you know what makes this channel different from the rest? You guide us through the approach and you don't explain the code. After watching the video I can code in like 5 minutes and I will never forget the solution. Thank you so much for all the videos and keep making quality voices. 🙂

[@debdutsaha4316]

Also I think so @Sushmita S Nataraj

[@jasasul8164]

I've never had so much fun watching an educational video, the backtracking steps explanation is so great Love your attitude, your persnoality and you explain things so well Great Video

[@BackToBackSWE]

thx

[@PatteeGreen]

You're addictive to watch, incredibly entertaining, and amazingly informative. Thanks!!

[@BackToBackSWE]

thank you. means a lot. Would love some feedback on the free 5 day course - backtobackswe.com/

[@trestenpool9045]

The code was tricky to wrap my head around. This helped very much, thank you!

[@milkthecode7369]

Man, great job with that explanation on the whiteboard. Having a mental model for this problem is hard enough, but explaining each step and having to make all those edits into a video must've been really tough. Thanks for your hard work!

[@BackToBackSWE]

nice - thx

[@pasankalansooriya3124]

Very attractive teaching style.good job sir

[@BackToBackSWE]

thanks

[@yicai7]

You are my Prof. Thanks for the awesome vid! Voted!

[@BackToBackSWE]

sure

[@RahulKumar_gr8]

There's a difference between understanding something and being able to make others understand the concept. Great job ! I Understood the concept of backtracking to a great extent.

[@BackToBackSWE]

great

[@Justin-cn3qu]

I just wanna say, great job.

[@BackToBackSWE]

thx

[@jeongtaebang3679]

For time complexity, can you please explain beyond the fact that there are n! permutations that need to be computed? I think the number of recursion calls is more than that, but not sure how to formally count this (also not sure if interviews will ask for that level of mathematical formalism)

[@BackToBackSWE]

The recurrence for generating permutations recursively is: T(n) = n * T(n-1) + O(1) where we just print the permutation (we don't copy a string to an answer list or anything). In each call, we will make n calls and n will reduce in size by 1. Each call will do at worst O(1) work. If n = 4 then we will see it concretely solves to n * (n - 1) * (n-2) * (n-3) where T(1) is a base case entailing a print. Does this make sense?

[@MarsTheProgrammer]

Your so fast paced that i got dizzy and nauseous watching you (plus with all the cuts), sorry couldn't follow anything you said..

[@BackToBackSWE]

no problem - old video, sorry

[@KrishnaKumar-jr7qq]

7:55 felt like watching Edge Of Tomorrow. LOL! But its great !!

[@BangMaster96]

This must have been exhausting to film.

[@Geopoliticalguy-z8n]

Is there any alt of recursion. Seriously this recursion is killing me...😢😢

[@biniyamasnake9756]

Good video. Learned the theory. It would have been nice to SEE the code and discuss tradeoffs of the different ways of programming the backtrack algorithm which is what I wanted but I like how you mentioned some of those ways.

[@BackToBackSWE]

Yeah. I realized this after I did it. Check this out: github.com/bephrem1/backtobackswe/issues/1 I will give this code and maybe do another video.

[@melaniemeza2139]

You are awesome!!

[@BackToBackSWE]

thx

[@chenchen55688]

I'm wondering if the time complexity is calculated as the total number of function calls, it would be exactly the number of nodes been traversed in the "tree." So that would be counted in such manner(from top of the tree, each term represents the number of nodes on each layer): N + N(N-1) + N(N-1)(N-2) … + N(N-1)(N-2)…(3) + N(N-1)(N-2)…(2) + N!, and this gets to e*N! as N gets large. Please correct me if I'm wrong. Thanks!

[@BackToBackSWE]

I'm not fully clear on the format of what you are summing

[@chenchen55688]

@@BackToBackSWE this might be clear imgur.com/a/dkUb8V1

[@iggykarpov]

Watching this at 0.75 speed seems pretty good. :)

[@BackToBackSWE]

thx sorry old vide

[@supremoluminary]

Thanks for that. I would like to see a code walkthrough next.

[@BackToBackSWE]

sure

[@dernyt-tpe]

A big thank you 😊

[@BackToBackSWE]

sure

[@saurabhdeshpande8450]

woahh....great energy man!!

[@BackToBackSWE]

old video - sorry

[@bibiworm]

He is one of the few people on KZbin who actually elaborate the concept of backtrack clearly. Great job!

[@Luka-se7sl]

Thanks God, that in word `boat` is 4 letter and not 5

[@BackToBackSWE]

yeah

[@beverlyukandu7189]

Suggestion: Try to stand on the opposite of the board you are writing. It's tough sometimes to take notes when you are standing directly in front of what you wrote out. Great job otherwise.

[@BackToBackSWE]

ok

[@JN-wj5tj]

ha ha! The artistic license with backtracking in the video is cute. The jumpiness of the video get's a little much. However, overall, the language used is clear and that makes understanding the approach easily understood ! Well done!

[@BackToBackSWE]

"The artistic license with backtracking in the video is cute." what and yeah sorry old video. and nice, surprising this one was rough, and thanks

[@akashm103]

why boat with 24 permutation , why not cat with 8 permutation, would have made your job easy.......... but hats off to your energy

[@BackToBackSWE]

I don't remember this video too much in detail, old video, bad mic, I was loud

[@boredasever6645]

why are you so frustrated with criticism in the comments. just don't reply it looks bad lol.

[@BackToBackSWE]

I don't remember what I said, this video is old. And that is fine.

[@242deepak]

If you would have not erased and drawn full recursion tree the understanding would have been better

[@BackToBackSWE]

yes

[@CodeSuccessChronicle]

you're DS god 🙏🙏🙏 love from India ❤

[@HeWhoShalNotBeNamed_]

huge respect for such massive amount of efforts exerted. very much appreciate them! for a beginner in recursion, very very helpful.

[@BackToBackSWE]

sure

[@frozen_tortus]

These permutations kind of remind me on generative recursion. Backtracking, I learn is for search? This bothers me sometime now.

[@BackToBackSWE]

ye

[@bhushanshinde8358]

Love ur energy n enthusiasm to get to depth of a problem rather than just solving the problems... Good job!

[@BackToBackSWE]

sure

[@kuralamuthankathirvelan]

Very Clear explanation , Thanks a lot bro . Looking for more DP videos .

[@BackToBackSWE]

sure

[@eve7947]

What if there are duplicate elements in the array, how do you avoid generating duplicate array for the answer?

[@BackToBackSWE]

We could just put the permutations in a HashSet but then again there is probably a smarter way to prune the placements going downwards. Reminds me of: leetcode.com/problems/subsets-ii/ I'll think on this.

[@roeekimmel]

At 11:00 I definitely could feel the mental struggle

[@backtobasics6865]

it would be good, if you can explain wrt code

[@BackToBackSWE]

yeah

[@divyanshuverma5652]

Sad that you are also like other KZbinrs as you are also solving the problem not explaining the code. I think code explanation is much much better but sadly I have to pay everywhere to get the code explanation.

[@BackToBackSWE]

I explain this in other videos and yeah people charge for (a minority share of) their work shocker

[@divyanshuverma5652]

@@BackToBackSWE Firstly thanks for replying and Yes people should charge for there work as they are spending a lot of time and effort but from a student point of view there are so many places to study but only some of them are good (like yours) that students like me got confused how to study and where to pay the charges as in starting everything works fine but at the end, it's all messed up and being a student its hard to pay everywhere to get the materials and learn. But you are doing a great job. Big thumbs up for you. 👍😁

[@user-zd1hj2lv3n]

When recursion makes that gym membership pay off 😂 Great explanation. Thanks

[@BackToBackSWE]

wut

[@mridulmittal5953]

never seen this much energy ! thanks dude

[@BackToBackSWE]

I'm a wild guy

[@riaagnes353]

Can you provide the code? I could not find the link.

[@BackToBackSWE]

yeah, it's been open on the github for a while as an issue

[@abudibro200]

Didn't know alexandre lacazette was a software engineer

[@afeaddeh2203]

If we used a StringBuilder instead of a Strings would the time efficiency be O(n!) and not O(n *n!)? I think that with StringBuilder we can just append the 'choice' in each frame instead of deep copying the String?

[@BackToBackSWE]

Im not sure I dont remember

[@PARUS1978]

Every time I listen your video I think need to set playback speed to 0.75%

[@BackToBackSWE]

sorry - old video i understand

[@adityamaurya8092]

Can we solve this problem without recursion

[@BackToBackSWE]

yes, but I don't remember how its coded. you can probably find a solution online

[@richduchin4098]

dude...keep it up! I could care less about the negative comments, ignore them. As a very seasoned software engineer, company founder, and exceptional teacher, I can safely say you have described this in the most laymen way possible. Excellent! Would love to connect with you and discuss a couple of things. Reach out to me on linkedin

[@BackToBackSWE]

This video is old haha, are the comments bad? I don't notice. I just respond to the stream that hits my notification bell. I don't use LinkedIn much, maybe email me? backtobackswe.com/contact

[@evanvinet8773]

this is not helpful at all. I was hoping to learn some string commands not some extremely basic theory

[@andrejivanovic8989]

this is dope you're doing a great job, keep it up

[@BackToBackSWE]

a lot of work ahead this year

[@z08840]

...I think it's about chinese room argument, but this is rather white board room...

[@airysm]

Is your old github repo with the solutions still available or is that behind Backtobackswe.com now?

[@rndmvds9765]

Here's my question. What if there is repeating letter in a string?

[@BackToBackSWE]

I don't remember but these's a way

[@aleyummusic]

Posting the code for this would be helpful

[@BackToBackSWE]

github.com/bephrem1/backtobackswe/issues/1 ;)

[@VinodKumar-pf1un]

what if the string length is 50 or something. Is there any way to calculate all the permutations in an efficient way for that case ?

[@BackToBackSWE]

I'm not sure

[@lianghe1401]

You are just so good at explaining those sort of ideas! The beauty of is I don't have to finish the video to get your idea. I stopped the video at 5 minutes and able to go back and resolve my problem.

[@BackToBackSWE]

great to hear!

[@krishnakrmahto97]

"No more decisions to make, backtrack" - this one was nice though.. :P

[@BackToBackSWE]

thanks

[@anujagrawal60]

Generally i don't comment, but dude this explanation is exceptional.I never understood string permutations this better. great work

[@BackToBackSWE]

welcome to commenting lol & thx

[@JOHNSMITH-ve3rq]

Definitely can't say 'do you even lift bro?' to this guy

[@fantasy9960]

wow thank you for such a great video!

[@virajkamat2764]

Time complexity of video O(Now!)

[@BackToBackSWE]

yes

[@kevinpatel5106]

you are awesome, I watch a lot of your videos for help!

[@MiddleEasternInAmerica]

superb 🔥🔥🔥🔥🔥🔥🔥🔥

[@BackToBackSWE]

thx

[@kylenelandenberger6482]

This is awesome. I totally understand it better than before. I am having a hard time putting this into recursion though. do you mind making the code live again?

[@BackToBackSWE]

Thanks and the repository is deprecated - we only maintain backtobackswe.com now.

[@sim77778777]

One of the best tutorials I have ever seen. Great job

[@BackToBackSWE]

Thanks

[@sergeivashchenko7308]

Great job man, you are really good at explaining

[@BackToBackSWE]

thanks!

[@EduSadiq]

What happened to you sir! You are speaking and delivery lecture extremely fast! You should deliver your lecture little bit slower... Your previous lecture were nice...

[@BackToBackSWE]

ok, let me go back and fix this, brb

[@AllanPichardo]

slow down lol

[@BackToBackSWE]

Old video - sorry. Things have to start somewhere.

[@ponrajkumarp6777]

how is space complexity O(n*n!) when we store in an array. we are storing the result so it should take O(n!). can you please explain. Thanks for the explanation.

[@BackToBackSWE]

I don't remember this to be honest

[@namanmishra3778]

Well, I guess n! is for the permutation purpose and n to print each permutation so that makes it O(n*n!). Not sure!!

[@ponrajkumarp6777]

@@namanmishra3778 Yea Whatever you are saying is for time complexity. but my doubt is about space complexity dude

[@snoopaku]

Great explanation, thank you so much! I have a question about the space complexity when we just print our permutations. The worst case is when we reach the bottom of our recursion and that would be O(n) because of n stack frames, I get it. But every stack frame also has its current state, I mean current permutation, which is also of length n in worst case. Am I right? Shouldn't space complexity in this case be O(n*n) = O(n^2)? Thanks a lot!

[@BackToBackSWE]

Yes, that would be the case, but if you pass a reference to a single mutable string (maybe make your own char array) you can keep the space linear (no copies in each frame of a whole structure).

[@snoopaku]

@@BackToBackSWE Yeah, you're right, thank you!

[@soft-tech7233]

super>>

[@BackToBackSWE]

thanks

[@jazzbandpiano]

the question is, how do you transfer your "running string" down the call stack without making a deep copy of it each time? Requires some trickery...

[@ZachWalz]

In your example, how would I figure out that “obat” is the 8th permutation without writing out all possible permutations that came before it?

[@BackToBackSWE]

So our original string will be "boat" . I immediately know that in the 1st slot the "b" will go first with a remainder of "oat", then the "o" with a remainder of "bat", then the "a" with a remainder of "bot", then the "t" with a remainder of "boa". That is what the first positioning will yield. So...4! = 24. We know that we will have 24 total permutations (for reasons I think this video explains...I did this a while back so not sure). So go back to what I was saying...."b" will go first with a remainder of "oat". With "b" in slot 1 (and 3 remaining slots)...I know for sure that I will be able to reap 6 permutations. Why? Well...3! = 6. So ok....we know that the 7th permutation will start with the "o" placed in the first slot with a remainder of "bat". So from there we can just do the enumeration and get there faster... We hopped to the 7th...and that is: o b a t _ _ _ _ If you followed this whole explanation then you should have a deeper understanding of what is happening.

[@vinnygouda2750]

Take a bow.......my brother what an effort

[@BackToBackSWE]

ye

[@VeereshPradeep]

Man there's some problem with this video. It just gets stuck buffering after first 20 seconds.

[@BackToBackSWE]

hm

[@ezpz4akash]

Seriously Man 😵

[@BackToBackSWE]

@@ezpz4akash yuh

[@chandraprakashsingh1039]

while writing the code you are looping over l to r but in helper fuction u will pass l+1 not i+1 like your rest of the backtracking videos.

[@BackToBackSWE]

where?

[@chandraprakashsingh1039]

@@BackToBackSWE void util(vector &A,vector &v,vector &sub,int data){ // if(data==A.size()){ v.push_back(sub); for(int i=data;i

[@chandraprakashsingh1039]

but, in case of string permutation void permute(string a, int l, int r) { // Base case if (l == r) cout

[@wl7497]

Great job! so for array permutation problem, the time complexity should O(n!), space complexity is O(n), n is the size of input array.

[@BackToBackSWE]

Which version?

[@mdsumon-ee5ke]

"exhausted all possibilities of x, no more backtrack"!!. Love your effort man, really. I finally understood backtracking! Yeah, I needed explanations 24 times! thank you :)

[@saruncse85]

Nice Explanation. Thank you.

[@BackToBackSWE]

sure

[@tmorid3]

You are great!!! 1 important thing - please put links to the previous videos of yours that you are referring to. It would really help. thanks!!

[@rodolfom.r9146]

Wow dude i had seen lot of tutorial but yours its the most amazing , clear and comprehensive ,thanks for take the time to do this , im subscribed now , greetings

[@pradeexsu]

thank you sir for great job. : ) plz make tutorial on the case when reapting char are there in string without reapting permutation like "Boom". it printed twice. how to avoid this reaptation without using "HashMap" and "Set".

[@BackToBackSWE]

ok

[@duhudu]

Thanks sir, first 4 minutes and got the idea how to solve it.

[@BackToBackSWE]

nice

[@shubhamjindal9214]

exactly same here ....! watched the video till 4:07 mins

[@BackToBackSWE]

@@shubhamjindal9214 haha nice

[@abdelrahman2348]

What is the difference between this problem and 6.9 in aziz's book ?

[@BackToBackSWE]

what was 6.9? I don't have the book up with me rn. I had to wipe my hard drive (had issues) and I'm setting shit back up again now...so yeah...I assume it is the same problem using an array? A string is an abstraction, it is an array of characters. It is a sequence. Any sequence can be permuted.

[@abdelrahman2348]

Back To Back SWE it’s okay and thanks for your attention...the problem of chapter 6 number 9 is Give an array A of n elements and a permutation p, apply p on A.. this part is easy to implement but the point is he said in the book any permutation can be viewed as a set of cyclic permutations for each element in the cycle how’d you identify if it has been permuted ..I didn’t understand what does it mean

[@BackToBackSWE]

@@abdelrahman2348 OHHHH, just pulled it up. Not it is not the same. And yeah, I just read the "Hint: Any permutation can be viewed as a set of cyclic permutations. For an element in a cycle, how would you identify if it has been permuted?" For this problem they say "A permutation can be specified by an array P". This is different from what we call a permutation in this problem. A permutation in that context is the codification of final positions for items. The "Hint" is that each permutation represents a series of interlinked steps to get all elements to their final positions so that O(1) space can be used (since it is trivial to perform the repositionings into a new array). These interlinked swaps form a series of "cycles" where we must swap an element in...then swap the element that sat where we just swappped into its final place...and so on... That is an odd way of saying it but yeah...that's the gist of it.

[@abdelrahman2348]

@@BackToBackSWE Thank you, but I still can't figure out it the permutation cycle , could you discuss it later in a video ?

[@BackToBackSWE]

@@abdelrahman2348 possibly

[@juniorcoder6988]

GREAT !!! I liked your lectures !

[@BackToBackSWE]

thanks

[@cocoarecords]

thanks !!

[@BackToBackSWE]

sure

[@ridhwaans]

what does a naive solution to this look like? without backtracking

[@BackToBackSWE]

As in an iterative approach? How would you brute force generating permutations?

[@norenpotsangbam7093]

Thanks bro really helpfull

[@BackToBackSWE]

Sure

[@atlantean.prince]

I like this guy

[@kishorkumarsingh9072]

Can i borrow some of your energy?

[@BackToBackSWE]

yeah, how much u want

[@bronzebond4869]

outstanding job dude. Over a year and i still go back to this

[@sanjivmadhavan5705]

man checking abs often:")

[@BackToBackSWE]

wat

[@dhee01]

Yoo.Thanks my man.This was really helpful.

[@gregoryrobertson]

I really enjoy learning from you, thank you for posting this.