We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Lexicographically Smallest Equivalent String

Difficulty: Medium

Problem Description

You are given two strings of the same length s1 and s2 and a string baseStr. We say s1[i] and s2[i] are equivalent characters. Your task is to return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2.

Key Insights

  • Equivalent characters can be grouped based on their relationships defined by s1 and s2.
  • The problem can be modeled as a graph where characters are nodes and edges represent equivalence.
  • Union-Find (Disjoint Set Union) data structure can efficiently manage the grouping of equivalent characters.
  • After forming groups, for each character in baseStr, replace it with the smallest character from its equivalence group.

Space and Time Complexity

Time Complexity: O(n) where n is the length of s1, s2, or baseStr (most operations take near constant time due to union-find optimizations). Space Complexity: O(1) additional space (not counting input and output), as we use the union-find structure to manage character relationships.

Solution

The solution uses the Union-Find (Disjoint Set Union) data structure to group equivalent characters based on the given strings s1 and s2. Each character is initially its own parent. As we iterate through the characters of s1 and s2, we union the pairs, effectively grouping them in the same set. After processing all pairs, we determine the smallest character in each equivalence class. Finally, for each character in baseStr, we find its representative in the union-find structure and replace it with the smallest character from its group.

Code Solutions

class UnionFind:
    def __init__(self):
        self.parent = {}
        
    def find(self, x):
        if x != self.parent.setdefault(x, x):
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.parent[rootY] = rootX

def smallestEquivalentString(s1: str, s2: str, baseStr: str) -> str:
    uf = UnionFind()
    
    for a, b in zip(s1, s2):
        uf.union(a, b)

    # Create a mapping for the smallest character in each group
    smallest = {}
    for char in uf.parent.keys():
        root = uf.find(char)
        if root not in smallest:
            smallest[root] = char
        else:
            smallest[root] = min(smallest[root], char)

    # Build the result based on the smallest equivalent characters
    result = []
    for char in baseStr:
        root = uf.find(char)
        result.append(smallest[root])
    
    return ''.join(result)
← Back to All Questions