Introduction

In this blog post, we will explore how to solve the LeetCode problem "1061" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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. For example, if s1 = "abc" and s2 = "cde", then we have 'a' == 'c', 'b' == 'd', and 'c' == 'e'. Equivalent characters follow the usual rules of any equivalence relation: Reflexivity: 'a' == 'a'. Symmetry: 'a' == 'b' implies 'b' == 'a'. Transitivity: 'a' == 'b' and 'b' == 'c' implies 'a' == 'c'. For example, given the equivalency information from s1 = "abc" and s2 = "cde", "acd" and "aab" are equivalent strings of baseStr = "eed", and "aab" is the lexicographically smallest equivalent string of baseStr. Return the lexicographically smallest equivalent string of baseStr by using the equivalency information from s1 and s2. Example 1: Input: s1 = "parker", s2 = "morris", baseStr = "parser" Output: "makkek" Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [m,p], [a,o], [k,r,s], [e,i]. The characters in each group are equivalent and sorted in lexicographical order. So the answer is "makkek". Example 2: Input: s1 = "hello", s2 = "world", baseStr = "hold" Output: "hdld" Explanation: Based on the equivalency information in s1 and s2, we can group their characters as [h,w], [d,e,o], [l,r]. So only the second letter 'o' in baseStr is changed to 'd', the answer is "hdld". Example 3: Input: s1 = "leetcode", s2 = "programs", baseStr = "sourcecode" Output: "aauaaaaada" Explanation: We group the equivalent characters in s1 and s2 as [a,o,e,r,s,c], [l,p], [g,t] and [d,m], thus all letters in baseStr except 'u' and 'd' are transformed to 'a', the answer is "aauaaaaada". Constraints: 1 <= s1.length, s2.length, baseStr <= 1000 s1.length == s2.length s1, s2, and baseStr consist of lowercase English letters.

Explanation

Here's a breakdown of the solution:

• Disjoint Set Union (DSU): The core idea is to use DSU to find the connected components of equivalent characters. Each character is initially in its own set. We iterate through s1 and s2, merging the sets of equivalent characters using the union operation.
• Find Representative: For each character in baseStr, we find the representative (root) of its set using the find operation. The representative will be the lexicographically smallest character in that set.

• Build Result: We construct the result string by replacing each character in baseStr with the representative of its equivalent set.

• Time Complexity: O(N + M), where N is the length of s1 (or s2) and M is the length of baseStr. The find and union operations in DSU effectively take O(1) time on average due to path compression and union by rank (although theoretically, it's inverse Ackermann, which is nearly constant). Space Complexity: O(1), since we use a fixed-size array of 26 elements for parent.

Code

    class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        parent = list(range(26))

        def find(x):
            if parent[x] == x:
                return x
            parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                if root_x < root_y:
                    parent[root_y] = root_x
                else:
                    parent[root_x] = root_y

        for i in range(len(s1)):
            union(ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a'))

        result = ""
        for char in baseStr:
            result += chr(find(ord(char) - ord('a')) + ord('a'))

        return result