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.
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:
'a' == 'a'.'a' == 'b' implies 'b' == 'a'.'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 <= 1000s1.length == s2.lengths1, s2, and baseStr consist of lowercase English letters.Problem Overview: You receive two strings s1 and s2 that define equivalence relationships between characters, plus a baseStr. If s1[i] equals s2[i], those characters belong to the same equivalence group. Replace each character in baseStr with the smallest lexicographical character from its equivalence group.
Approach 1: Union-Find (Disjoint Set) (Time: O((n + m) * α(26)), Space: O(26))
This approach models each lowercase letter as a node in a Union Find structure. For every pair (s1[i], s2[i]), perform a union operation to merge their sets. The key detail: always attach the larger character root to the smaller one so the representative of each set is the lexicographically smallest character. After building the structure, iterate through baseStr, find the root for each character using find(), and append that root to the result. Since the alphabet size is fixed (26), union and find operations are extremely fast with path compression.
This method is both simple and optimal. The disjoint-set structure automatically groups equivalent characters and guarantees that the representative element is the smallest possible character.
Approach 2: DFS Graph Traversal (Time: O(26 + m + n), Space: O(26 + m))
You can also treat the problem as a graph. Each character is a node, and each pair (s1[i], s2[i]) forms an undirected edge. Build an adjacency list connecting equivalent characters. Then run DFS to discover connected components. For each component, compute the smallest character and assign it as the representative for every node in that component.
After preprocessing, iterate through baseStr and replace each character with the smallest mapped value from its component. DFS works well because the graph is tiny (only 26 nodes), making traversal very cheap. The extra adjacency list storage slightly increases memory usage compared to Union-Find.
Recommended for interviews: The Union-Find approach is what interviewers usually expect. It directly models equivalence relationships and demonstrates familiarity with disjoint set structures. The DFS graph approach still shows strong understanding of connected components in a string transformation problem, but Union-Find is cleaner and easier to implement under interview pressure.
The idea is to use a union-find data structure to record the equivalence relationships between characters. The union operation will merge sets of equivalent characters.
Next, for each character, we find its representative in the equivalence class (or set), and map each character to the lexicographically smallest character in its set, thus ensuring the smallest equivalent transformation.
This implementation initializes a union-find structure to keep track of the parent of each character (where each unique character starts as its own parent). By performing union operations on pairs of characters from s1 and s2, we merge equivalent sets.
In the final step, we find the parent of each character in baseStr and construct the smallest equivalent string.
Time Complexity: O(N + M), where N is the length of s1 and s2, and M is the length of baseStr.
Space Complexity: O(ALPHABET_SIZE), which is constant due to the fixed size of the alphabet.
Another method is treating each character as a node in a graph where edges connect equivalent nodes (characters). Perform Depth-First Search (DFS) to find all characters that belong to an equivalence group.
Once we have gathered all groups and established the smallest character for each group, we can form the desired output by mapping each baseStr character to the smallest in its equivalence class.
This Python function constructs a graph from the equivalences given in s1 and s2. It then performs DFS to determine the connected components of the graph, which represent equivalence classes. After identifying each group, it maps all characters in the group to their minimum character to construct the smallest equivalent string for baseStr.
Python
Time Complexity: O(N + M), where N is the length of s1 and s2, and M is the number of edges in the graph (size of baseStr).
Space Complexity: O(ALPHABET_SIZE), due to the storage of graph nodes and mappings.
We can use Union Find (Disjoint Set Union, DSU) to handle the equivalence relations between characters. Each character can be regarded as a node, and the equivalence relations can be seen as edges connecting these nodes. With Union Find, we can group all equivalent characters together and quickly find the representative element for each character during queries. When performing union operations, we always set the representative element to be the lexicographically smallest character. This ensures that the final string is the lexicographically smallest equivalent string.
The time complexity is O((n + m) times log |\Sigma|) and the space complexity is O(|\Sigma|), where n is the length of strings s1 and s2, m is the length of baseStr, and |\Sigma| is the size of the character set, which is 26 in this problem.
| Approach | Complexity |
|---|---|
| Union-Find Approach | Time Complexity: O(N + M), where N is the length of Space Complexity: O(ALPHABET_SIZE), which is constant due to the fixed size of the alphabet. |
| DFS Graph Approach | Time Complexity: O(N + M), where N is the length of Space Complexity: O(ALPHABET_SIZE), due to the storage of graph nodes and mappings. |
| Union Find | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Union-Find (Disjoint Set) | O((n + m) * α(26)) | O(26) | Best general solution for equivalence relations; clean and optimal for grouping characters. |
| DFS Graph Traversal | O(26 + m + n) | O(26 + m) | Useful when modeling the problem explicitly as a graph and exploring connected components. |
Lexicographically Smallest Equivalent String | Using DFS | Leetcode 1061 | codestorywithMIK • codestorywithMIK • 15,066 views views
Watch 9 more video solutions →Practice Lexicographically Smallest Equivalent String with our built-in code editor and test cases.
Practice on FleetCode