hi, let Avik connect you.


** You can give your thought about this content and request modifications if needed from Ask For Modifications page. Thank You.

** You can check all the posts on the Posts page.

** More about me in the About Me section.

Lexicographically Smallest Equivalent String


  • Approach:

    1. If we see the conditions given for equivalence characters, we can represent a connection between two nodes.

    2. This leads us to build a graph of characters.

    3. Now from 26 characters, we will find the corresponding lexicographically smallest character and store them for future usage.

    4. While finding the lexicographically smallest for a character say, X, if we find some other characters linked to X directly or mutually, we will also assign them the lexicographically smallest character.

    5. Now for each character of the baseStr, we will replace them corresponding lexicographically smallest character.

    6. Return the changed string.


  • Time and Space Complexity:

      • Time Complexity: O(N)

      • Space Complexity: O(N)


Code [C++]

class Solution {

public:


void findMin(int node, vector<vector<int>>&graph, int & ans, vector<int>&mapChar){

if(mapChar[node] != -1) {

ans = min(ans, node);

return;

}

ans = min(ans, node);

mapChar[node] = ans;

for(int i=0; i<graph[node].size(); i++){

int child = graph[node][i];

// if(mapChar[child] != -1) continue;

findMin(child, graph, ans, mapChar);

}

}


string smallestEquivalentString(string s1, string s2, string baseStr) {

vector<vector<int>>graph(26);

int n = s1.size(), m = baseStr.size();

for(int i=0; i<n; i++){

graph[s1[i]-'a'].push_back(s2[i]-'a');

graph[s2[i]-'a'].push_back(s1[i]-'a');

}


vector<int>mapChar(26, -1);

for(int i=0; i<26; i++){

if(mapChar[i] == -1){

int ans = i;

findMin(i, graph, ans, mapChar);

// mapChar[i] = ans;

}

}

for(int i=0; i<m; i++){

baseStr[i] = mapChar[baseStr[i] - 'a'] + 'a';

}

return baseStr;

}

};