# 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/

## Comments

## Back To Back SWE

AuthorTable 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.)

## B.DevSoftTech

Authorsuper>>

## the arclight

AuthorVery attractive teaching style.good job sir

## M3дуZa

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

## aditya maurya

AuthorCan we solve this problem without recursion

## Bored Asever

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

## snoopaku

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

## Sushmitha Bhat

AuthorWho else feels that this channel deserves more subscribers?

## Murmad Man

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

## Kylene Landenberger

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

## Milk The Code

AuthorMan, 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!

## Ashwini Abhishek

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

## Melanie Meza

AuthorYou are awesome!!

## Elviro Pardillo

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

## Shobhit Agarwal

Authorit would be good, if you can explain wrt code

## Ashish Magar

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

## Bhushan Shinde

AuthorLove ur energy n enthusiasm to get to depth of a problem rather than just solving the problems…

Good job!

## Saurabh Deshpande

Authorwoahh….great energy man!!

## Yi Cai

AuthorYou are my Prof.

Thanks for the awesome vid! Voted!

## Arvind K

AuthorGood job Bro!

## Akash Mishra

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

## crashxxx

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

## Pradeep Suthar

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

## Yang Yu

Authorlove the ENERGY my guy – earned a sub

## abhi sable

Authorbro also explain complete code for the same

## Yao Wang

AuthorLike a rap

## vaishali bisht

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

## Beverly Ukandu

AuthorSuggestion: 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.

## SIVA SAI KUMAR REDDY Kalava

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

## EduSadiq

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

## Rich Duchin

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

## Subhana Khan

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

## Austin Callaghan

Authorset playback speed to 0.75. You're welcome (:

## Vijay Kiran

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

## Kishor Kumar Singh

AuthorCan i borrow some of your energy?

## Sanjiv Madhavan

Authorman checking abs often:")

## Justin

AuthorI just wanna say, great job.

## El Gallo

Author11: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

reallyappreciate you putting yourself through that on video because it fully and completely demonstrates the intuition behind the code.## CHANDRA PRAKASH SINGH

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

## piyush ohri

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

## ria agnes

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

## Dayem Siddiqui

AuthorTest 2:00

## LALIT KUMAR MEHTA

Authorthanks a lot

## Sumit kumar

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