8 Permutation of Strings | Backtracking Solution
Вставка
- Опубліковано 11 гру 2023
- 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.geeksforgeeks.org/problem...
------------------------------------------------------------------------------------------
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.
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.
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.
Great video. BT never felt this easy
Was waiting for this videos after the last 😊
Was waiting for the video.... thanks a lot
Thanks a lot bhaiya for such great videos... bs bhaiya tree aur graph ki series aur laa do finall request bhaiya..
Hello Sir, Please complete this series. It is really helpful
Very well explained. So basically, here the flow is similar to DFS here right and not BFS, just wanted to clarify that?
Graphs and Trees please🙏
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
Thank you Aditya Verma Salute 🥷
please make a video of Trees and Graph also.. ❣
you're one of best
It's showing 2 unavailable videos. Is there any video published after permutation question ?
Awsome video maza aa gaya
Kindly complete the dp series... you missed some patterns mentioned in 1 st video
To ab main sum string wala ques kr paunga gfg pe?
thank you.
SIr, please complete this series.....
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
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.
Bhaiya aapsae request hai aapk tree and graph ki series aur pda do please bhaiya..
Hello sir, recently I completed your recursion playlist so next what should I start your backtracking playlist or your DP playlist.
DP then BT
Nice
Watched the video and successfully solved permutation 1 and 2 of the leetcode
me too
volume thoda high m record kiya kro, full volumne m bhi low lgti h
this code is working even if we pass the string by value ...why??
Aditya bro, Voice thodi low hai video ki, please increase it a bit if possible, thank you so much
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
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.
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.
❤❤❤❤❤❤
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]));
*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
waiting for generating unique permutations.
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
Subarrays with Sum ‘k' please help me with this problem'
15:15 main video starts here
Trees padhlo bhai...striver ki pattern samajh nahi a raha hai
Tree Tree Tree Please please please
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!).
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?
ye kaisi baat kr rahi hai aap devi ji🤓
tree
Bhai itni coding ki kuch kan nhi aaya
Kyu 24 batch ka h?