Problem statement

https://leetcode.com/problems/lexicographically-smallest-equivalent-string/

Solution

We need to create graph and then traverse it with dfs (or bfs) and find all connected components. Then for each element we find the smallest letter in its component.

Complexity

Time complexity is O(n + E), space complexity is O(n + E) as well.

Code

class Solution:
    def smallestEquivalentString(self, A, B, S):
        G = defaultdict(list)
        for x, y in zip(A, B):
            if x == y: continue
            G[x] += [y]
            G[y] += [x]

        V, comps = set(), defaultdict(list)
        
        def dfs(node, i):
            V.add(node)
            comps[i].append(node)
            for neib in G[node]:
                if neib not in V:
                    dfs(neib, i)

        cnt, parents = 0, {}
        for node in G.keys():
            if node not in V:
                dfs(node, cnt)
                cnt += 1

        for i in comps.keys():
            mn = min(comps[i])
            for j in comps[i]:
                parents[j] = mn

        return "".join(parents.get(i, i) for i in S)