8 Permutation of Strings | Backtracking Solution

Given a string S. The task is to print all unique permutations of the given string in lexicographically sorted order.
Example 1:
Input: ABC
Output:
ABC ACB BAC BCA CAB CBA
Explanation:
Given string ABC has permutations in 6
forms as ABC, ACB, BAC, BCA, CAB and CBA .
Example 2:
Input: ABSG
Output:
ABGS ABSG AGBS AGSB ASBG ASGB BAGS
BASG BGAS BGSA BSAG BSGA GABS GASB
GBAS GBSA GSAB GSBA SABG SAGB SBAG
SBGA SGAB SGBA
Explanation:
Given string ABSG has 24 permutations.
Your Task:
You don't need to read input or print anything. Your task is to complete the function find_permutation() which takes the string S as input parameter and returns a vector of string in lexicographical order.
Expected Time Complexity: O(n! * n)
Expected Space Complexity: O(n! * n)
Problem Statement: www.geeksforge...
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻‍💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻‍♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.

[@wiselife5821]

mai ek week se struggle kar raha tha dhang ki recursion video ke liye bcoz mai bilkul hi beginner hu. trust me maine boht time lagaya hai recursion samajhne mei . duniya bhar ki videos dekh li par ab jake recursion samajh aya hai(recursion ki playlist bhi dekhi hai fir backtracking par aya hu). to commment likhna to banta hai. jab maine ye backtracking ka code khud se likh diya tab mai pagal ho gaya or agaya comment likhne . shukriya aditya bhai. tum humara bhala kr rhe to tumhara bhala hone se koi nahi rok sakta.

[@dsaa2z]

Hello Sir, I had also started a series for dsa using python on youtube. I am trying to complete strivers atoz sheet. I am deeply impressed by your teaching style. Thanks for creating such awesome content.

[@ritwikvaidya5754]

One small detail he missed which I found while tying Permutations question on Leetcode. In the backtracking step, you need to do mp.erase(s[i]) in addition to swap(s[start],s[i]). If you don't do this, the recursive tree will get pruned after the very first character itself.

[@JangBahadur3028]

Was waiting for this videos after the last 😊

[@saumyagaur7633]

Great video. BT never felt this easy

[@Raj10185]

Watched the video and successfully solved permutation 1 and 2 of the leetcode

[@GoluKumar-sb2si]

me too

[@prrockzed]

Was waiting for the video.... thanks a lot

[@rishabhahuja7413]

Graphs and Trees please🙏

[@anushakandagal1727]

An extra check condition can be applied to avoid some redundant function calls, if 2 chars are same there is no point in swapping them/undo the swapping class Solution { public: vectorfind_permutation(string S) { // Code here there set ans; permutations(S,0,ans); vector vc(ans.begin(), ans.end()); return vc; } void permutations(string &s, int start, set &ans){ if(start == s.size()-1){ ans.insert(s); return; } unordered_map mp; for(int i = start; i < s.size(); i++){ if(mp.find(s[i]) == mp.end()){ mp[s[i]]++; if(s[i] != s[start]){ swap(s[i],s[start]); permutations(s,start+1,ans); // backtracking step swap(s[i],s[start]); } else permutations(s,start+1,ans); } } } }; This solution works on gfg practice question www.geeksforgeeks.org/problems/permutations-of-a-given-string2041/1

[@049bite_gauravkumarsoni3]

please make a video of Trees and Graph also.. ❣

[@anutoshghosh7893]

Very well explained. So basically, here the flow is similar to DFS here right and not BFS, just wanted to clarify that?

[@gamingbeast3555]

aur bhaiya aapsase pdnae kae baad aur practice kae baad questions ho rhae hain mjhsae.. thanks a lot bhaiya when i will get offer i will meet you bhaiyaa

[@sumitbasu5146]

Thank you Aditya Verma Salute 🥷

[@gamingbeast3555]

Thanks a lot bhaiya for such great videos... bs bhaiya tree aur graph ki series aur laa do finall request bhaiya..

[@randomsongs8835]

Hello Sir, Please complete this series. It is really helpful

[@bommakantibeeraiah1486]

private static List permutations(String s) { List ans=new ArrayList(); int idx=0; solve(idx,s.toCharArray(),ans); return ans; } private static void solve(int idx,char[] s, List ans) { if(idx==s.length-1) { String str=""; for(char c:s) { str+=c; } ans.add(str); return; } Set st=new HashSet(); for(int i=idx;i

[@jaspalsharma7426]

Sir, please also make video on graph

[@AjayThakur-gu9hg]

Kindly complete the dp series... you missed some patterns mentioned in 1 st video

[@divyranjan254]

the unordered set shown in recursive code at 2:40 needs to be declared globally or passed by reference just like the vector to store answers because in the current code, each recursive call would form a new unordered_set making its purpose to avoid repetition useless.

[@srajanratti8093]

No that would stop exploration further. You can try coding. I did the same and was not getting all the results. We only want to limit on a particular level.

[@kullumanali-bu8uf]

you're one of best

[@abdulmohsin1]

Aditya bro, Voice thodi low hai video ki, please increase it a bit if possible, thank you so much

[@sadafkausar8770]

Hello sir, recently I completed your recursion playlist so next what should I start your backtracking playlist or your DP playlist.

[@surajsingh-sm7qx]

DP then BT

[@Doraemon67812]

Bhaiya campus se placement hua tha pr offer letter revoke ho gya bhot jagah job ke liye apply kar chuka hu pr response nhi aa rha please koi job bta do

[@saurabhjalutharia]

volume thoda high m record kiya kro, full volumne m bhi low lgti h

[@Prateek_Mantry]

thank you.

[@TanuKansal-nn4el]

It's showing 2 unavailable videos. Is there any video published after permutation question ?

[@abhi224505]

Not sure string will work in case of javascript. Maybe we can just use array in javascript, as it is pass by value. function find_permutation(arr) { const res = []; const swap = (arr, i, j) => { [arr[i], arr[j]] = [arr[j], arr[i]]; }; function solve(arr, start) { if (start === arr.length) { res.push([...arr]); } let map = {}; for (let i = start; i < arr.length; i++) { if (!map[arr[i]]) { map[arr[i]] = true; swap(arr, start, i); solve(arr, start + 1); swap(arr, start, i); } } } solve(arr, 0); return res; } console.log(find_permutation([1, 2, 3, 3]));

[@raunakgiri21]

*Converting the string to array makes it work* find_permutation(S){ //code here let res = []; let strArr = S.split(''); const swapCharacters = (index1, index2) => { let t = strArr[index1]; strArr[index1] = strArr[index2]; strArr[index2] = t; } const backtrack = (ind) => { if(ind === strArr.length) { res.push(strArr.join('')); return; } const map = new Map(); for(let i=ind;i

[@Raj10185]

Awsome video maza aa gaya

[@eshaansharma145]

The time complexity (TC) of the provided code is O(N * N!), where N is the length of the input string S. Here's the breakdown: Sorting the input string takes O(N * log(N)) time. The backtracking algorithm generates all permutations, and there are N! possible permutations for a string of length N. For each permutation, the function makes swaps and checks for duplicates, contributing to a linear factor of N for each permutation. Therefore, the overall time complexity is O(N * log(N) + N * N!). The dominating factor is N!, making the time complexity effectively O(N * N!).

[@pranabpaul6317]

The average case time complexity of an unordered_set is O(1) and worst case O(n), here we can also use the unordered_set as we don't need to maintain sorted order in the set. So why you are taking O(logn) in account and also sorting?

[@gurupreetsingh8347]

Nice

[@aniketsharma472]

SIr, please complete this series.....

[@deepanshuverma6237]

Permutation of a List of Integers in java : private static void solve(int idx, List s, List ans) { if (idx == s.size() - 1) { ans.add(new ArrayList(s)); return; } Set st = new HashSet(); for (int i = idx; i < s.size(); i++) { if (!st.contains(s.get(i))) { st.add(s.get(i)); Collections.swap(s, idx, i); solve(idx + 1, s, ans); Collections.swap(s, idx, i); } } }

[@kullumanali-bu8uf]

this code is working even if we pass the string by value ...why??

[@gamingbeast3555]

Bhaiya aapsae request hai aapk tree and graph ki series aur pda do please bhaiya..

[@kalpagarwal8291]

waiting for generating unique permutations.

[@pratik9449]

15:15 main video starts here

[@xiaoshen194]

To ab main sum string wala ques kr paunga gfg pe?

[@ratneshtiwari2028]

Subarrays with Sum ‘k' please help me with this problem'

[@_desouvik]

[@SaurabhMishraa]

❤❤❤❤❤❤

[@siddarthchidurula5931]

Trees padhlo bhai...striver ki pattern samajh nahi a raha hai

[@sumitbasu5146]

Tree Tree Tree Please please please

[@abhayjoshi362]

ye kaisi baat kr rahi hai aap devi ji🤓

[@ratneshtiwari2028]

tree

[@Doraemon67812]

Bhai itni coding ki kuch kan nhi aaya

[@xiaoshen194]

Kyu 24 batch ka h?