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
What character we place in a “slot”
None really…but at each decision point we will have fewer characters to work with because of our previous decisions.
Let n be the string length. Place n characters.
Time: O(n * n!)
– There are n! permutations and it takes O(n) time to add each one to our result array
– 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).
Success In Tech: