Watch 10 video solutions for Lexicographically Smallest Equivalent String, a medium level problem involving String, Union Find. This walkthrough by codestorywithMIK has 15,066 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |