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

[@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 =)

[@DED_Search]

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

[@optimizedpran1247]

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

[@BackToBackSWE]

hahaha same

[@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

[@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

[@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!

[@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

[@vishalcelestine8654]

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

[@BackToBackSWE]

thanks haha

[@bronzebond4869]

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

[@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 :)

[@bhushanshinde8358]

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

[@BackToBackSWE]

sure

[@yangyu4489]

love the ENERGY my guy - earned a sub

[@BackToBackSWE]

thx

[@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

[@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

[@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

[@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

[@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!!

[@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

[@pranavverma2397]

best lecture for this question on the entire KZbin

[@debanjanasantra6724]

Appreciate the enthusiasm to explain all the 24 combos !!

[@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

[@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

[@HeWhoShalNotBeNamed_]

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

[@BackToBackSWE]

sure

[@supremoluminary]

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

[@BackToBackSWE]

sure

[@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.

[@sim77778777]

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

[@BackToBackSWE]

Thanks

[@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/

[@BangMaster96]

This must have been exhausting to film.

[@trestenpool9045]

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

[@mridulmittal5953]

never seen this much energy ! thanks dude

[@BackToBackSWE]

I'm a wild guy

[@pasankalansooriya3124]

Very attractive teaching style.good job sir

[@BackToBackSWE]

thanks

[@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.

[@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

[@yicai7]

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

[@BackToBackSWE]

sure

[@vinnygouda2750]

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

[@BackToBackSWE]

ye

[@kevinjaypatel]

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

[@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?

[@minirasamedova648]

I like how passionate you are about teaching ^^ thank you very much for the video !!

[@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

[@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?

[@gregoryrobertson]

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

[@dhee01]

Yoo.Thanks my man.This was really helpful.

[@Justin-cn3qu]

I just wanna say, great job.

[@BackToBackSWE]

thx

[@andrejivanovic8989]

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

[@BackToBackSWE]

a lot of work ahead this year

[@sergeivashchenko7308]

Great job man, you are really good at explaining

[@BackToBackSWE]

thanks!

[@Geopoliticalguy-z8n]

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

[@maximilianokalaydjian7452]

Amazing video! You're really helping me to crack the coding interviews!

[@saravanansarangan7035]

Great explanation bro hats off for your patience

[@BackToBackSWE]

ok

[@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

[@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...

[@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

[@aleyummusic]

Posting the code for this would be helpful

[@BackToBackSWE]

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

[@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

[@user-zd1hj2lv3n]

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

[@BackToBackSWE]

wut

[@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!

[@airysm]

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

[@frozen_tortus]

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

[@BackToBackSWE]

ye

[@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

[@krishnakrmahto97]

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

[@BackToBackSWE]

thanks

[@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

[@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

[@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?

[@fantasy9960]

wow thank you for such a great video!

[@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.

[@KrishnaKumar-jr7qq]

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

[@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.

[@CodeSuccessChronicle]

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

[@backtobasics6865]

it would be good, if you can explain wrt code

[@BackToBackSWE]

yeah

[@saruncse85]

Nice Explanation. Thank you.

[@BackToBackSWE]

sure

[@penj4369]

Love the energy !

[@juniorcoder6988]

GREAT !!! I liked your lectures !

[@BackToBackSWE]

thanks

[@rndmvds9765]

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

[@BackToBackSWE]

I don't remember but these's a way

[@roeekimmel]

At 11:00 I definitely could feel the mental struggle

[@melaniemeza2139]

You are awesome!!

[@BackToBackSWE]

thx

[@dernyt-tpe]

A big thank you 😊

[@BackToBackSWE]

sure

[@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

[@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

[@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

[@kuralamuthankathirvelan]

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

[@BackToBackSWE]

sure

[@JOHNSMITH-ve3rq]

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

[@saurabhdeshpande8450]

woahh....great energy man!!

[@BackToBackSWE]

old video - sorry

[@242deepak]

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

[@BackToBackSWE]

yes

[@norenpotsangbam7093]

Thanks bro really helpfull

[@BackToBackSWE]

Sure

[@arvindk4813]

Good job Bro!

[@BackToBackSWE]

thx

[@PARUS1978]

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

[@BackToBackSWE]

sorry - old video i understand

[@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

[@atlantean.prince]

I like this guy

[@abudibro200]

Didn't know alexandre lacazette was a software engineer

[@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

[@Luka-se7sl]

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

[@BackToBackSWE]

yeah

[@sanjivmadhavan5705]

man checking abs often:")

[@BackToBackSWE]

wat

[@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

[@cocoarecords]

thanks !!

[@BackToBackSWE]

sure

[@lalitkumarmehta6026]

thanks a lot

[@BackToBackSWE]

sure

[@MiddleEasternInAmerica]

superb 🔥🔥🔥🔥🔥🔥🔥🔥

[@BackToBackSWE]

thx

[@virajkamat2764]

Time complexity of video O(Now!)

[@BackToBackSWE]

yes

[@soft-tech7233]

super>>

[@BackToBackSWE]

thanks