8 Permutation of Strings | Backtracking Solution

Рет қаралды 21,364

Күн бұрын

Пікірлер: 59

@wiselife5821 10 ай бұрын

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.

@sangamsamdarshi4634 Ай бұрын

What an analogy, it was a great analogy about the clothes, changing or simply swapping the positions of a person that was really great

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

@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 7 ай бұрын

me too

@prrockzed Жыл бұрын

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

@anushakandagal1727 9 ай бұрын

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

@SYYddwww Ай бұрын

he already used set for this case.

@049bite_gauravkumarsoni3 Жыл бұрын

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

@anutoshghosh7893 11 ай бұрын

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

@divyranjan254 10 ай бұрын

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 7 ай бұрын

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.

@nsudhir_here 3 ай бұрын

@@srajanratti8093 You have to remove added character from map in backtracking to make it work.

@AAKASHAGARWAL-sx8cc Ай бұрын

@@srajanratti8093 makes sense , had the same doubt, thanks

@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

@ritwikvaidya5754 10 ай бұрын

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.

@aaryansingh2004 Ай бұрын

It works fine for me without erasing...

@gamingbeast3555 Жыл бұрын

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

@kullumanali-bu8uf Жыл бұрын

you're one of best

@randomsongs8835 Жыл бұрын

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

@rishabhahuja7413 Жыл бұрын

Graphs and Trees please🙏

@sumitbasu5146 9 ай бұрын

Thank you Aditya Verma Salute 🥷

@AjayThakur-gu9hg Жыл бұрын

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

@saurabhjalutharia Жыл бұрын

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

@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

@aniketsharma472 Жыл бұрын

SIr, please complete this series.....

@TanuKansal-nn4el Жыл бұрын

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

@bommakantibeeraiah1486 10 ай бұрын

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

@Raj10185 Жыл бұрын

Awsome video maza aa gaya

@jaspalsharma7426 5 ай бұрын

Sir, please also make video on graph

@abhi224505 10 ай бұрын

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 10 ай бұрын

*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

@pratik9449 Жыл бұрын

15:15 main video starts here

@gamingbeast3555 Жыл бұрын

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

@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

@Prateek_Mantry 9 ай бұрын

thank you.

@kullumanali-bu8uf Жыл бұрын

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

@kalpagarwal8291 8 ай бұрын

waiting for generating unique permutations.

@xiaoshen194 Жыл бұрын

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

@deepanshuverma6237 6 ай бұрын

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); } } }

@gurupreetsingh8347 Жыл бұрын

Nice

@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 11 ай бұрын

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?