How To Permute A String - Generate All Permutations Of A String @BackToBackSWE
How To Permute A String - Generate All Permutations Of A String  @BackToBackSWE
Uploaded December 2018 | Updated November 2026, 1 hour ago
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: youtube.com/channel/UCOf7UPMHBjAavgD0Qw5q5ww

Tuschar Roy: youtube.com/user/tusharroy2525

GeeksForGeeks: youtube.com/channel/UC0RhatS1pyxInC00YKjjBqQ

Jarvis Johnson: youtube.com/user/VSympathyV

Success In Tech: youtube.com/channel/UC-vYrOAmtrx9sBzJAf3x_xw

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

This question is number 16.3 in the fantastic book "Elements of Programming Interviews" by Adnan Aziz
How To Permute A String - Generate All Permutations Of A StringMerge 2 Sorted Lists - A Fundamental Merge Sort Subroutine (Merge Two Sorted Lists on LeetCode)Count Total Unique Binary Search Trees - The nth Catalan Number (Dynamic Programming)Coding Interview | QuickSort Overview #shorts #datastructures #codinginterviewWhat is Hashing? | Hashtables Explained #datastructures #hashtableIntroducing Asymptotic NotationsImplement A Sudoku Solver - Sudoku Solving Backtracking Algorithm (Sudoku Solver on LeetCode)The IP Address Decomposition Problem - Compute All Valid IP Addresses From Raw IP StringDijkstras Algorithm vs Prims AlgorithmTest If A Binary Tree Is Height Balanced (Balanced Binary Tree on LeetCode)Deeply Understanding Logarithms In Time Complexities & Their Role In Computer ScienceEdit Distance Between 2 Strings - The Levenshtein Distance (Edit Distance on LeetCode)
Back To Back SWE |

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

SHARE TO X SHARE TO REDDIT SHARE TO FACEBOOK WALLPAPER