Lexicographically Smallest Equivalent String | Using DFS | Leetcode 1061 | codestorywithMIK

Hi Everyone, this is the 13th video of our Playlist "Graphs : Popular Interview Problems".
Now we will be solving a good Graph practice problem - Lexicographically Smallest Equivalent String | Using DFS | Leetcode 1061 | codestorywithMIK

The video contains my detailed thought process and a simple approach to this Problem.
If you have been following my "Graph Concepts & Qns" playlist , then these Qns will become very easy. Today we will solve it using DFS.
Further we will solve it using the BFS and Disjoint Set Union (DSU) approach as well.

Problem Name : Lexicographically Smallest Equivalent String | Using DFS | Leetcode 1061 | codestorywithMIK
Company Tags :

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

Video Summary :
This approach builds a graph connecting equivalent characters from s1 and s2. For each character in baseStr, it uses DFS to explore all connected characters and finds the lexicographically smallest one in its connected component. This smallest character is then used to form the resulting string.

✨ Timelines✨
00:00 - Introduction
0:32 - Understand the problem
7:20 - Intuition building
08:32 - Dry Run Example
11:47 - Time Complexity
12:25 - Story to Code Live

#MIK #mik #Mik
#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 #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[RG-hmer]

I just wish you put the solution of every leetcode problem
Wonderful explanation

[codestorywithMIK]

If you guys need separate videos for BFS approach and DSU Approach, do let me know.

Thank you all
❤🙏🏻

[atifhu]

after seeing your yesterday's challenge video explanation, today I liked your video even without watching completely.

[souravjoshi]

The best part is that you explain the Qn so well, half solution is already done by then 🔥

[nimishgupta]

bhai... khud se kar diya mene... yakeen nahi ho raha hai...
disjoint set wale code ko modify karke kar diya mene
thanks a lot

[indianengineer]

I think in this approach of DFS instead of doing loop on all chars of baseStr, do DFS on all char from a to z and store the answer in an array of size 26. Then fill the finalBaseStr.

[indianengineer]

Union Find Code :


/*
1. Modified the union logic by prioritizing smallest ascci as leader
2. Find function is same
3. While doing union of strings, do uion of parents not the individual strings,
4. Because no path compression is there while doing union so you have to use parent for that ---> union(parentX, parentY, parent);
*/

class Solution {
public String s1, String s2, String baseStr) {
int[] rank = new int[26];
int[] parent = new int[26];
for(int i = 0; i < 26; i++) parent[i] = i;
int n = s1.length();
int m = baseStr.length();
for(int i = 0; i < n; i++){
int ch1 = s1.charAt(i) - 'a';
int ch2 = s2.charAt(i) - 'a';
int parentX = find(ch1, parent);
int parentY = find(ch2, parent);
union(parentX, parentY, parent);
}
StringBuilder ans = new StringBuilder();
for(int i = 0; i < m; i++){
int charIndex = baseStr.charAt(i) - 'a';
int index = find(charIndex, parent);
char ch = (char)(index + 'a');
ans.append(ch);
}
return ans.toString();
}

int find(int x, int[] parent){
if(parent[x] == x){
return x;
}
return parent[x] = find(parent[x], parent);
}

void union(int x, int y, int[] parent){
int xParent = find(x, parent);
int yParent = find(y, parent);

if(x == y) return;

else if(x > y){
parent[x] = y;
}else{
parent[y] = x;
}
}
}

[yashmundra]

I was trying to manually add the transitivity edge and got failed at some test case with memory error, learned that dont try to add additional complexity in the solution, question will be solved by the concepts itself, !!!, thank you so much

[chiragsingh]

You have become my favourite now❤.
Pls start uploading concepts+some questions videos for each topics like u did for graphs and then a seperate playlist for its questions only too.!
Thankyou for being such an amazing teacher MIK❤

[Himanshhhhxu]

I got scared of problem statement, didn't understand problem statement clearly, about to see your video but took my pen and paper and started visualising just like you, and boom🔥 problem solved on my ownnn, i always watch your videos to learn something new, your teaching skills are exceptional, just one request bhaiya try to cover some Leetcode weekly questions also🙏

[hemant_kumar_]

DSU Approach -> Union By Size and Union By Lexical Order


class DSU{
public:
vector<int> size, parent;
DSU(int n){
size.resize(n+1, 1);
parent.resize(n+1);

for(int i=0;i<n;i++){
parent[i]=i;
}
}
int findParent(int node){
if(node == parent[node]) return node;
return
}

void UnionBySize(int u, int v){
int u_parent = findParent(u);
int v_parent = findParent(v);

if(u_parent == v_parent) return;

if(size[u_parent] > size[v_parent]){
parent[v_parent]=u_parent;

}
else if(size[u_parent] <= size[v_parent]){
parent[u_parent]=v_parent;

}
}
void UnionByLex(int u, int v) {
int u_parent = findParent(u_parent);
int v_parent = findParent(v_parent);

if (u_parent == v_parent) return;

// Keep the smaller character as root
if (u_parent < v_parent)
parent[v_parent] = u_parent;
else
parent[u_parent] = v_parent;
}
};

class Solution {
public:

string s1, string s2, string baseStr) {

DSU dsu(26);
unordered_map<int, vector<int>> adj;
for (int i = 0; i < s1.size(); ++i) {
int u = s1[i] - 'a';
int v = s2[i] - 'a';
dsu.UnionBySize(u, v);
// dsu.UnionByLex(u, v);
}

string result;
// DSU -> Union By Size
for (char ch : baseStr) {
int root = dsu.findParent(ch - 'a');
for(int i=0;i<26;i++){
if(dsu.findParent(i) == root){
result += (char)(i + 'a');
break;
}
}

}

// DSU -> Union By Lexical Order
for (char ch : baseStr) {
int root = dsu.findParent(ch - 'a');
result += (char)(root + 'a');
}
return result;
}
};

[ayushsharma]

Really nice explanation. Though if we find lexicographical smallest character for all 26 alphabets and save it some where instead of calling dfs on the baseStr, we can reduce the time complexity from 26*(V+E)---->(V+E). This become efficient when we have a baseStr.length()> 26 say 100 then we are calling dfs just 26 times . (Credits: chatGPT )

[udaytewary]

Really bhaiya you are great by first seeing the question I am not able to understand the question then I knew you are there I was waiting for your solution then after that I was able to understand the question and for that I will always thankful to you

[AnkitYadav-kzei]

coding is fun, if there is editorial like this😇, never stop making videos

[JJ-tpdd]

Apkaa hi wait tha.. comment kr diya ab video dekhta hu..thanks

[sumitgupta]

DSU approach : class Solution {
public:
int find(int x, vector<int> parent) {
if (parent[x] != x) {
parent[x] = find(parent[x], parent);
}

return parent[x];
}
void Union(int x, int y, vector<int>& parent) {
int px = find(x, parent);
int py = find(y, parent);
if (px == py)
return;
if (px < py)
parent[py] = px;
else
parent[px] = py;
}
string s1, string s2, string baseStr) {
vector<int> parent(26);
for (int i = 0; i < 26; i++) {
parent[i] = i;
}

for (int i = 0; i < s1.length(); i++) {
Union(s1[i] - 'a', s2[i] - 'a', parent);
}
string ans = "";
for (int i = 0; i < baseStr.length(); i++) {
ans += find(baseStr[i] - 'a', parent) + 'a';
}
return ans;
}
};

[AnjuGupta-szuk]

I solved this question by my own after watching your graph playlist but by using DSU 😀

[souravjoshi]

Far Far better than Leetcode official solution bro. legit

[harsh-singh]

wow brother, I was not able to understand from leetcode discussion. But you had mad it very easy. 👍🏻👍🏻

[hemant_kumar_]

// DFS Approach
class Solution {
public:
int DFS(int node, unordered_map<int, vector<int>> &adj, vector<int> &vis){
vis[node]=1;
int mini=node;
for(auto it : adj[node]){
if(!vis[it]){
mini = min(mini, DFS(it, adj, vis));
}
}
return mini;
}
string s1, string s2, string baseStr) {
unordered_map<int, vector<int>> adj;
for (int i = 0; i < s1.size(); ++i) {
int u = s1[i] - 'a';
int v = s2[i] - 'a';
adj[u].push_back(v);
adj[v].push_back(u);
}

// DFS
string result;
for(char ch : baseStr){
vector<int> vis(26, 0);
int node = ch-'a';
int smallestEqv = DFS(node, adj, vis);
result+=(char)(smallestEqv + 'a');
}
return result;
}
};.