Custom Sort String | 2 Approaches | Intuition | Meta | Leetcode 791

This is the 35th Video of our Playlist "Strings : Popular Interview Problems".
In this video we will try to solve a very good string problem : Custom Sort String | 2 Approaches | Intuition | Meta | Leetcode 791

Share your learnings on LinkedIn, Twitter (X), Instagram, Facebook(Meta) with the hashtag #codestorywithmik & feel free to tag me.

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Custom Sort String | 2 Approaches | Intuition | Meta | Leetcode 791
Company Tags : META (Facebook)

Approach Summary :
Approach-1:

Approach-2:
This approach utilizes a comparator to sort the characters in the string `str` based on their positions in the specified order. It initializes a vector `index` to store the positions of characters in the order. The sorting is performed using the `sort` function with a lambda comparator. The time complexity is O(nlogn) due to the sorting operation, and the space complexity is O(26) ~ O(1) as the vector `index` is of constant size. This approach provides an alternative solution by directly sorting the characters based on the specified order.

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

✨ Timelines✨
00:00 - Introduction
04:18 - Approach-1
10:43 - Approach-2
22:09 - Coding it up

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #2024 #newyear

[ankitsingh]

what a consistency you have i am following you daily

[bhuppidhamii]

हमें इतना ज्ञान प्रदान करें, आपका बहुत-बहुत धन्यवाद |
रमज़ान की शुभकमनाये

भगवान आपको हमेशा आशीर्वाद दें

[EB-otuu]

your explanation easily beats the explanation of other famous youtubers. extremely underrated you are

[sayantanpoddar]

glad that i have found this a amazing consistency🔥🔥🔥🔥

[Code_loading]

Bhaiya please try to bring comparators for java too🙏❤

[wearevacationuncoverers]

Anyone having confusion that since we have initialised the index with -1, it will come first during custom sort, notice that the lambda will be called by sort utility and it will be called only for characters present in the str and hence the characters (ch1, ch2) present in the str will be sorted as per the index and remaining which are left will be appended in the end.
auto lambda = [&index](char &ch1, char &ch2) {
return index[ch1-'a'] < index[ch2-'a'];
};

[deepakdass]

Learnt comparators today. Thank you sir

[ankit]

first very thaknful to you what you provide us if you provide solution of contest problems then it will very helpful for us again its my only request if you have time complexity then no problem

[swagboltey]

11:10 Java ke liye comparators chahiye bro❤

[tusharnanda]

class Solution {
public:
string customSortString(string order, string s) {
vector<int> mp(26, 0);
for(int i = 0 ; i < order.size() ; i++) mp[order[i]-'a'] = i+1;
sort(s.begin(), s.end(), [&](char &a, char &b){return mp[a-'a']<mp[b-'a'];});
return s;
}
};

[abhishektripathi]

I used a min heap to store the pairs of indexes and their corresponding characters from string s in ascending order
class Solution {
public:
string customSortString(string order, string s) {
vector<int>mp(26, -1);
for(int i = 0; i < order.length(); i++){
mp[order[i]-'a'] = i;
}
priority_queue<pair<int, char>, vector<pair<int, char>>, greater<pair<int, char>>>pq;
string ans = "";

for(int i = 0; i < s.length(); i++){
if(mp[s[i]-'a'] != -1){
pq.push({mp[s[i]-'a'], s[i]});
}
else{
ans.push_back(s[i]);
}
}

while(!pq.empty()){
char topChar = pq.top().second;
pq.pop();
ans.push_back(topChar);
}
return ans;
}
};

[oqant]

POTD DONE

THANKS A LOT 🙌
[11.3.24] ✅✅

[souravjoshi]

Thanks a lot for in-depth contents.
Can you please make yesterday contest problem-3 ?

[fourthdimension]

amazing just next level explanation bro

[ugcwithaddi]

Thank you so much. I had already watched your comparators video.
Can you confirm if Recursion Concepts playlist is complete ??

[AYJ]

you can use indexOf also
Java :
public String customSortString(String order, String s) {
int N = s.length();

Character[] sArr = new Character[N];
for(int i = 0; i < N; i++){
sArr[i] = s.charAt(i);
}

Arrays.sort(sArr, (a, b) -> {
return order.indexOf(a) - order.indexOf(b);
});

String res = "";
for(int i = 0; i < N; i++){
res += sArr[i];
}
return res;
}
Kotlin :
fun customSortString(order: String, s: String): String {
return
}

[User-student-]

after learning concept coded on own : class Solution {
public:
string customSortString(string order, string s) {
unordered_map<char, int> mp;
string res="";
for(char c : s){
mp[c]++;
}
for(char c : order){
if(mp.find(c)!=mp.end()){
int count=mp[c];
for(int i=0;i<count;i++){
res=res+c;
}
mp[c]=0;
}
}

for(auto pair :mp){
if(pair.second>0){
for(int i=0;i<pair.second;i++){
res=res+pair.first;
}
}
}
return res;

}
};

[chitranshjain]

Can you make a video on
Count no of pair of xor in a given range lc 1804
Trie&bit manipulation

[perfectcopy]

Bhaiya Comparartor In JAVA ka Video Jldi le aao Aap.. :)

[mahimagupta]

Sir please Bring daily coding leetcode challenge solutions per day