How To Permute A String - Generate All Permutations Of A String
VloĆŸit
- Äas pĆidĂĄn 27. 12. 2018
- Free 5-Day Mini-Course: backtobackswe.com
Try Our Full Platform: backtobackswe.com/pricing
đč 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 - VÄda a technologie
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.)
pro trick: you can watch series at flixzone. Me and my gf have been using them for watching lots of of movies lately.
@Jase Harold Yea, been using flixzone} for since december myself =)
I want to get "No More Decisions To Make Backtrack" tattooed on my arm after this.
hahaha same
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
thx
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!
nice - thx
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.
sure thx
He is one of the few people on CZcams who actually elaborate the concept of backtrack clearly. Great job!
love the ENERGY my guy - earned a sub
thx
Love ur energy n enthusiasm to get to depth of a problem rather than just solving the problems...
Good job!
sure
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.
great to hear!
Amazing explanation, I have a interview coming up and i will keep this in mind for any permutation problem!
love
Who else feels that this channel deserves more subscribers?
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 CZcams 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.
@@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. đ
Also I think so @Sushmita S Nataraj
"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 :)
outstanding job dude. Over a year and i still go back to this
Write a code to count number of ânowâs in this video! đ
Just kidding, good tutorial
I say that a lot. Weird mannerism. I can't control them....well I could consciously try...eh...whatever
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
never seen this much energy ! thanks dude
I'm a wild guy
Amazing video!
You're really helping me to crack the coding interviews!
I like how passionate you are about teaching ^^
thank you very much for the video !!
you are awesome, I watch a lot of your videos for help!
The code was tricky to wrap my head around. This helped very much, thank you!
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
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.
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.
You're addictive to watch, incredibly entertaining, and amazingly informative. Thanks!!
thank you. means a lot. Would love some feedback on the free 5 day course - backtobackswe.com/
this is dope you're doing a great job, keep it up
a lot of work ahead this year
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.
sure
I really enjoy learning from you, thank you for posting this.
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!!
Appreciate the enthusiasm to explain all the 24 combos !!
huge respect for such massive amount of efforts exerted. very much appreciate them! for a beginner in recursion, very very helpful.
sure
Not the teacher we deserve, but the teacher we need..hats off !!!
thanks haha
Thanks for that. I would like to see a code walkthrough next.
sure
Great job man, you are really good at explaining
thanks!
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!
"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
Generally i don't comment, but dude this explanation is exceptional.I never understood string permutations this better. great work
welcome to commenting lol & thx
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?
Thanks and the repository is deprecated - we only maintain backtobackswe.com now.
You are my Prof.
Thanks for the awesome vid! Voted!
sure
best lecture for this question on the entire CZcams
One of the best tutorials I have ever seen. Great job
Thanks
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
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
Great explanation bro hats off for your patience
ok
I just wanna say, great job.
thx
Yoo.Thanks my man.This was really helpful.
Nice Explanation. Thank you.
sure
wow thank you for such a great video!
GREAT !!!
I liked your lectures !
thanks
When recursion makes that gym membership pay off đ Great explanation. Thanks
wut
Jeez, I thought he is going to write a code :(
Here Is My Response: backtobackswe.com/im-sorry
Github: github.com/bephrem1/backtobackswe/issues/1
Thanks sir, first 4 minutes and got the idea how to solve it.
nice
exactly same here ....!
watched the video till 4:07 mins
@@shubhamjindal9214 haha nice
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".
ok
Love the energy !
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)
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?
Take a bow.......my brother
what an effort
ye
woahh....great energy man!!
old video - sorry
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.
Which version?
Very attractive teaching style.good job sir
thanks
"No more decisions to make, backtrack" - this one was nice though.. :P
thanks
Is your old github repo with the solutions still available or is that behind Backtobackswe.com now?
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!
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).
@@BackToBackSWE Yeah, you're right, thank you!
7:55 felt like watching Edge Of Tomorrow. LOL! But its great !!
You are awesome!!
thx
In your example, how would I figure out that âobatâ is the 8th permutation without writing out all possible permutations that came before it?
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.
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.
great
A big thank you đ
sure
Good job Bro!
thx
Very Clear explanation , Thanks a lot bro . Looking for more DP videos .
sure
Is there any alt of recursion. Seriously this recursion is killing me...đąđą
This must have been exhausting to film.
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 ?
I'm not sure
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!
I'm not fully clear on the format of what you are summing
@@BackToBackSWE
this might be clear
imgur.com/a/dkUb8V1
These permutations kind of remind me on generative recursion. Backtracking, I learn is for search? This bothers me sometime now.
ye
Can you provide the code? I could not find the link.
yeah, it's been open on the github for a while as an issue
Thanks bro really helpfull
Sure
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?
Im not sure I dont remember
thanks !!
sure
I like this guy
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...
What if there are duplicate elements in the array, how do you avoid generating duplicate array for the answer?
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.
Watching this at 0.75 speed seems pretty good. :)
thx sorry old vide
thanks a lot
sure
what does a naive solution to this look like? without backtracking
As in an iterative approach? How would you brute force generating permutations?
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.
I don't remember this to be honest
Well, I guess n! is for the permutation purpose and n to print each permutation so that makes it O(n*n!). Not sure!!
@@namanmishra3778 Yea Whatever you are saying is for time complexity. but my doubt is about space complexity dude
man checking abs often:")
wat
Posting the code for this would be helpful
github.com/bephrem1/backtobackswe/issues/1
;)
you're DS god đđđ love from India â€
Definitely can't say 'do you even lift bro?' to this guy
it would be good, if you can explain wrt code
yeah
superb đ„đ„đ„đ„đ„đ„đ„đ„
thx
What is the difference between this problem and 6.9 in aziz's book ?
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.
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
@@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.
@@BackToBackSWE Thank you, but I still can't figure out it the permutation cycle , could you discuss it later in a video ?
@@abdelrahman2348 possibly
Can we solve this problem without recursion
yes, but I don't remember how its coded. you can probably find a solution online
super>>
thanks
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.
ok
Every time I listen your video I think need to set playback speed to 0.75%
sorry - old video i understand
If you would have not erased and drawn full recursion tree the understanding would have been better
yes
Here's my question. What if there is repeating letter in a string?
I don't remember but these's a way
Thanks God, that in word `boat` is 4 letter and not 5
yeah
Didn't know alexandre lacazette was a software engineer
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.
where?
@@BackToBackSWE void util(vector &A,vector &v,vector &sub,int data){
// if(data==A.size()){
v.push_back(sub);
for(int i=data;i
but, in case of string permutation
void permute(string a, int l, int r)
{
// Base case
if (l == r)
cout
why boat with 24 permutation , why not cat with 8 permutation, would have made your job easy.......... but hats off to your energy
I don't remember this video too much in detail, old video, bad mic, I was loud
Man there's some problem with this video. It just gets stuck buffering after first 20 seconds.
hm
Seriously Man đ”
@@ezpz4akash yuh
bro also explain complete code for the same
ok
Time complexity of video O(Now!)
yes