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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Lexicographically Smallest Equivalent String

Number: 1058

Difficulty: Medium

Paid? No

Companies: Cloudera

Problem Description

Given two strings s1 and s2 of equal length that define pairs of equivalent characters and a baseStr, transform baseStr by replacing each character with the lexicographically smallest equivalent character based on the equivalency relation defined by s1 and s2.

Key Insights

  • Use the Union Find (Disjoint Set Union) data structure to model the equivalence relation between characters.
  • Initialize each character as its own parent.
  • For every pair (s1[i], s2[i]), perform a union operation. Always attach the larger lexicographical character to the smaller one so that the root always represents the smallest equivalent character.
  • For each character in baseStr, find its corresponding smallest representative by performing the find operation.
  • Efficient union-find operations with path compression help achieve fast query times.

Space and Time Complexity

Time Complexity: O(n + m * α(n)), where n is the length of s1 (or s2) for union operations, m is the length of baseStr for find operations, and α is the inverse Ackermann function (nearly constant). Space Complexity: O(1) or O(26) for the union-find parent array since we only work with 26 lowercase letters.

Solution

The solution uses the Union Find algorithm:

  1. Initialize an array (or map) "parent" for all 26 lowercase letters, where each element initially points to itself.
  2. For each pair of characters from s1 and s2, perform a union operation. The union is done such that the root always holds the lexicographically smallest character among the connected components.
  3. Use path compression in the find operation to speed up future queries.
  4. For every character in baseStr, replace it with the find result from the union-find structure, which gives the smallest equivalent character.

Data structures used: array of size 26 (for parents), and use of union-find algorithm.

Code Solutions

# Python solution using Union-Find with path compression
class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        # Initialize parent for each character (0-25 represent 'a'-'z')
        parent = list(range(26))
        
        # Define the find function with path compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        # Define the union function ensuring the root is lexicographically smallest
        def union(x, y):
            rootX = find(x)
            rootY = find(y)
            if rootX == rootY:
                return
            # Always attach the larger lexicographical root to the smaller one
            if rootX < rootY:
                parent[rootY] = rootX
            else:
                parent[rootX] = rootY

        # Process each pair of characters from s1 and s2
        for ch1, ch2 in zip(s1, s2):
            union(ord(ch1)-ord('a'), ord(ch2)-ord('a'))
        
        # Build the result using the smallest equivalent character for every letter in baseStr
        result = []
        for ch in baseStr:
            smallest_char = chr(find(ord(ch)-ord('a')) + ord('a'))
            result.append(smallest_char)
            
        return "".join(result)

# Example usage:
# sol = Solution()
# print(sol.smallestEquivalentString("parker", "morris", "parser"))  # Output: "makkek"
← Back to All Questions