Công Nghệ

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




Free 5-Day Mini-Course:
Try Our Full Platform:
📹 Intuitive Video Explanations
🏃 Run Code As You Learn
💾 Save Progress
❓New Unseen Questions
🔎 Get All Solutions
Subscribe To Live Tech Offers:
Join Our Coaching Service:

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:

Tuschar Roy:

GeeksForGeeks:

Jarvis Johnson:

Success In Tech:

++++++++++++++++++++++++++++++++++++++++++++++++++

This question is number 16.3 in the fantastic book “Elements of Programming Interviews” by Adnan Aziz

Nguồn: https://vinhtrinh.com.vn

Xem thêm bài viết khác: https://vinhtrinh.com.vn/cong-nghe/

Công Nghệ
Lego Racers (Nintendo 64) Walkthrough
Công Nghệ
Minecraft Pe | Top 5 câu lệnh cơ bản nhất trong MC | HakuMC
Công Nghệ
Học Excel 2: 1.2.2. Kết hợp các hàm LEFT, LEN trong nhóm hàm Text
  • 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: https://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.)


  • super>>


  • Very attractive teaching style.good job sir


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


  • Can we solve this problem without recursion


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


  • 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!


  • Who else feels that this channel deserves more subscribers?


  • You talk wayyyyyyyyyyyy too much. Abstract concepts with one impelementation. Focus on the problem at hand and the base concept


  • 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?


  • 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!


  • Thanks for explaining, yours is one of the best algorithms channels I have come across in my many years of journey with youtube. You deserve more subscribers.


  • You are awesome!!


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


  • it would be good, if you can explain wrt code


  • got irritated with "and now" and cutting frames until 6:09, cannot concentrate anymore further


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


  • woahh….great energy man!!


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


  • Good job Bro!


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


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


  • 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".


  • love the ENERGY my guy – earned a sub


  • bro also explain complete code for the same


  • Like a rap


  • Hey..It will be really helpful if you can do a video on combination sum. Its backtracking is bit different. Link https://leetcode.com/problems/combination-sum/
    Thank you


  • 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.


  • he could have explained whole thing in half the time or even less,but he took more time


  • 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…


  • 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


  • If you can kindly talk little slower that would really help. Otherwise everything is perfect


  • set playback speed to 0.75. You're welcome (:


  • +1 for editing , +50 for content , +100 for delivery


  • Can i borrow some of your energy?


  • man checking abs often:")


  • I just wanna say, great job.


  • 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.


  • 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.


  • Sir , Provide explanation along with code , that will help us to figure out how to implement backtracking in our code.


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


  • Test 2:00


  • thanks a lot


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