[Leetcode] 1061. Lexicographically Smallest Equivalent String

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

initial

I solved it. I was like what ds do i use to store this? Somehow we need to get the lowest ascii value or character for a subset of characters. So it is like c->a

Union find!

sol

I struggled a little bit with converting from char to ascii value and vice versa. Look at the code

ALSO, v impt that you need to find_parent for each character in baseStr. Cuz the parent information might not be fully updated because of path compression:

**For example, suppose you merged a and c early, then later added b to the same group.

The parent array might still have parent[b]=c, not parent[b]=a.**

so it shouldnt be
tmp+=chr(parent[i] + ord('a'))

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        n = len(baseStr)
        parent = [i for i in range(26)]
        
        def find_parent(node,parent):
            if parent[node]!=node:
                parent[node]=find_parent(parent[node],parent)
            return parent[node]

        def union(node1,node2):
            par1 = find_parent(node1,parent)
            par2 = find_parent(node2,parent)
            if par1<par2:
                parent[par2]=par1
            else:
                parent[par1]=par2
        
        for i in range(len(s1)):
            c1,c2=s1[i],s2[i]
            c1,c2=ord(c1)-ord('a'),ord(c2)-ord('a')
            union(c1,c2)
        print(parent)
        tmp=""
        for i in baseStr:
            par = find_parent(ord(i)-ord('a'),parent)
            tmp+=chr(par + ord('a'))
        return tmp

sol using dict

more convienent

class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        # Union-Find using dictionary
        UF = {}

        def find(x):
            # Initialise UF[x] to itself if not already present
            if x not in UF:
                UF[x] = x
            # Path compression
            if UF[x] != x:
                UF[x] = find(UF[x])
            return UF[x]

        def union(x, y):
            # Find roots of both x and y
            rootX = find(x)
            rootY = find(y)
            # Always set the parent to the smaller character
            if rootX > rootY:
                UF[rootX] = rootY
            else:
                UF[rootY] = rootX

        # Union the pairs from s1 and s2
        for a, b in zip(s1, s2):
            union(a, b)

        # Build the result using the smallest equivalent character
        result = []
        for c in baseStr:
            result.append(find(c))  # This ensures we get the lex smallest rep
        return "".join(result)

complexity

find and union is almost constant time with o(alpha(n)) where alpha (n) is the inverse ackermann function and is almost constant (1) cuz of path compression

so time is o(n+m) where n=len(s1) and m=len(baseStr)

space is o(26) + o(m)