Lexicographically Smallest Equivalent String

Med

#1013Time: O(N + M), where N is the length of `s1` and `s2`, and M is the length of `baseStr`. Building the graph takes O(N). Finding all connected components and their representatives takes O(V + E) where V=26 is the number of vertices and E is the number of edges (at most N), so it's O(N). Building the result string takes O(M). The total is O(N + M).Space: O(N + M). The adjacency list can store up to 2*N edges, taking O(N) space. The `mapping` and `visited` arrays take O(C) (constant, since C=26) space. The recursion stack for DFS or queue for BFS takes O(C) space in the worst case. The result string builder takes O(M) space. Thus, the total space is O(N + M + C), which simplifies to O(N + M).1 company

Algorithms

Union Find

Data structures

String

Companies

Cloudera

Prompt

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.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach models the character equivalences as a graph. Each of the 26 lowercase English letters is a node. An edge exists between two characters if they are declared equivalent in s1 and s2. The problem then reduces to finding the connected components of this graph. For each character in baseStr, we find which component it belongs to and replace it with the lexicographically smallest character in that component.

Algorithm

Create an adjacency list to represent the graph of 26 characters. An array of lists List<Integer>[] adj is suitable.
Iterate through s1 and s2 to populate the adjacency list with undirected edges for each equivalent pair.
Initialize a mapping array of size 26, where mapping[i] will store the representative for character 'a' + i.
Initialize a visited array of size 26 to keep track of visited nodes during traversal.
Iterate from 'a' to 'z' (or index 0 to 25). If a character c has not been visited:
- Start a graph traversal (e.g., Depth First Search) from c.
- Keep track of all characters visited in this traversal (the component) and find the minimum character in this component.
- After the traversal completes for a component, update the mapping for all characters in that component to the minimum character found.
Create a StringBuilder to build the result.
Iterate through baseStr. For each character, find its representative from the mapping array and append it to the StringBuilder.
Return the string from the StringBuilder.

Walkthrough

We can represent the relationships as a graph where characters are vertices and equivalences are edges. Since the equivalence relation is symmetric, the graph is undirected.

Graph Construction: We build an adjacency list for the 26 lowercase letters. We iterate through s1 and s2 simultaneously. For each index i, we add an edge between s1[i] and s2[i].
Find Components and Representatives: We need to find the connected components, which represent the equivalence classes. For each component, we must also find its lexicographically smallest character. We can do this by iterating through all 26 characters. If a character hasn't been assigned to a component yet, we start a graph traversal (like DFS or BFS) from it. The traversal will find all characters in the same component. During the traversal, we keep track of the smallest character encountered. Once the traversal is complete, all characters found belong to the same equivalence class, and their representative is the smallest character found.
Map and Build Result: We use a mapping array to store the representative for each character. After identifying a component and its smallest character, we update the mapping for all characters in that component. Finally, we iterate through baseStr, look up the representative for each character in our mapping array, and build the lexicographically smallest equivalent string.

1import java.util.*;2 3class Solution {4    public String smallestEquivalentString(String s1, String s2, String baseStr) {5        // Step 1: Build the graph using an array of lists6        List<Integer>[] adj = new ArrayList[26];7        for (int i = 0; i < 26; i++) {8            adj[i] = new ArrayList<>();9        }10        for (int i = 0; i < s1.length(); i++) {11            int u = s1.charAt(i) - 'a';12            int v = s2.charAt(i) - 'a';13            adj[u].add(v);14            adj[v].add(u);15        }16 17        // Step 2: Find components and their representatives18        int[] mapping = new int[26];19        boolean[] visited = new boolean[26];20 21        for (int i = 0; i < 26; i++) {22            if (!visited[i]) {23                List<Integer> component = new ArrayList<>();24                int minCharIndex = i;25                26                Stack<Integer> stack = new Stack<>();27                stack.push(i);28                visited[i] = true;29                30                while (!stack.isEmpty()) {31                    int u = stack.pop();32                    component.add(u);33                    minCharIndex = Math.min(minCharIndex, u);34                    35                    for (int v : adj[u]) {36                        if (!visited[v]) {37                            visited[v] = true;38                            stack.push(v);39                        }40                    }41                }42                43                for (int nodeIndex : component) {44                    mapping[nodeIndex] = minCharIndex;45                }46            }47        }48 49        // Step 3: Build the result string50        StringBuilder result = new StringBuilder();51        for (char c : baseStr.toCharArray()) {52            result.append((char) ('a' + mapping[c - 'a']));53        }54 55        return result.toString();56    }57}

Complexity

Time

O(N + M), where N is the length of `s1` and `s2`, and M is the length of `baseStr`. Building the graph takes O(N). Finding all connected components and their representatives takes O(V + E) where V=26 is the number of vertices and E is the number of edges (at most N), so it's O(N). Building the result string takes O(M). The total is O(N + M).

Space

O(N + M). The adjacency list can store up to 2*N edges, taking O(N) space. The `mapping` and `visited` arrays take O(C) (constant, since C=26) space. The recursion stack for DFS or queue for BFS takes O(C) space in the worst case. The result string builder takes O(M) space. Thus, the total space is O(N + M + C), which simplifies to O(N + M).

Trade-offs

Pros

Conceptually straightforward, as it directly models the problem of finding equivalence classes as finding connected components in a graph.
Correctly handles all properties of an equivalence relation (reflexivity, symmetry, transitivity) through the nature of connected components.

Cons

Requires more space compared to the Union-Find approach, as it needs to store the entire graph structure (adjacency list).
The implementation can be slightly more complex, involving explicit graph traversal logic and state management (e.g., a visited array).

This approach uses a Union-Find data structure, which is highly efficient for problems involving partitioning a set into disjoint subsets (equivalence classes). Each character is initially in its own set. We then iterate through the given equivalences and merge the sets of equivalent characters. The lexicographically smallest character in each merged set becomes the representative for that set.

Algorithm

Initialize a parent array of size 26, such that parent[i] = i for all i. This represents 26 disjoint sets, one for each character.
Implement the find(i) operation with path compression. This operation finds the root of the set containing element i and flattens the tree structure along the way for future efficiency.
Implement the union(i, j) operation. It finds the roots of i and j. If they are different, it merges the two sets by making the lexicographically smaller root the parent of the larger one. This ensures the root of any set is always its smallest element.
Iterate through s1 and s2 from i = 0 to N-1. For each pair of characters c1 = s1.charAt(i) and c2 = s2.charAt(i), call union(c1 - 'a', c2 - 'a').
Create a StringBuilder to build the result.
Iterate through baseStr. For each character c, find its representative by calling find(c - 'a'). Append the character corresponding to this representative to the StringBuilder.
Return the string from the StringBuilder.

Walkthrough

The Union-Find (or Disjoint Set Union) data structure is perfectly suited for this problem. It efficiently manages partitions of a set and supports two main operations: finding the representative of a set (find) and merging two sets (union).

Initialization: We use a parent array of size 26 for the 26 lowercase letters. Initially, each character is in its own set, so we set parent[i] = i for i from 0 to 25.
Processing Equivalences: We iterate through s1 and s2. For each pair of characters (s1[i], s2[i]), we call union on their corresponding integer indices. The union operation merges the sets of the two characters. To ensure the representative of a set is always its smallest character, when merging, we make the smaller root the parent of the larger root.
Optimizations: The find operation is implemented with path compression. When we find the root of an element, we make all nodes on the path point directly to the root. This significantly speeds up future find operations, leading to a nearly constant amortized time complexity.
Constructing the Result: After processing all equivalences in s1 and s2, the parent array holds the final structure of equivalence classes. To build the result, we iterate through baseStr. For each character, we call find to get the root of its set, which is its lexicographically smallest equivalent character. We append this character to our result string.

1class Solution {2    private int[] parent;3 4    // Find operation with path compression5    private int find(int i) {6        if (parent[i] == i) {7            return i;8        }9        return parent[i] = find(parent[i]);10    }11 12    // Union operation13    private void union(int i, int j) {14        int rootI = find(i);15        int rootJ = find(j);16        if (rootI != rootJ) {17            // Merge the set with the larger representative into the one with the smaller one18            if (rootI < rootJ) {19                parent[rootJ] = rootI;20            } else {21                parent[rootI] = rootJ;22            }23        }24    }25 26    public String smallestEquivalentString(String s1, String s2, String baseStr) {27        // Step 1: Initialize Union-Find structure28        parent = new int[26];29        for (int i = 0; i < 26; i++) {30            parent[i] = i;31        }32 33        // Step 2: Process equivalences by uniting sets34        for (int i = 0; i < s1.length(); i++) {35            union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');36        }37 38        // Step 3: Build the result string39        StringBuilder result = new StringBuilder();40        for (char c : baseStr.toCharArray()) {41            result.append((char) ('a' + find(c - 'a')));42        }43 44        return result.toString();45    }46}

Complexity

Time

O((N + M) * α(C)), where N is the length of `s1`, M is the length of `baseStr`, C=26 is the alphabet size, and α is the very slow-growing Inverse Ackermann function. For all practical purposes, α(C) can be considered a small constant (less than 5). Thus, the effective time complexity is linear, O(N + M).

Space

O(M). The `parent` array for the Union-Find structure takes O(C) space, where C=26 is the alphabet size, which is constant. The space for the result string is O(M). Therefore, the total space complexity is O(C + M), which simplifies to O(M).

Trade-offs

Pros

Extremely efficient in both time and space.
Uses a very small, constant amount of extra space (O(1) as the alphabet size is fixed at 26) besides the output string.
The implementation is concise and elegant for this class of problems.

Cons

The Union-Find data structure and its optimizations (path compression) might be less familiar than simple graph traversal to some developers.

Solutions

Solution

1public class Solution { public string SmallestEquivalentString ( string s1 , string s2 , string baseStr ) { int [] p = new int [ 26 ]; for ( int i = 0 ; i < 26 ; i ++) { p [ i ] = i ; } int Find ( int x ) { if ( p [ x ] != x ) { p [ x ] = Find ( p [ x ]); } return p [ x ]; } for ( int i = 0 ; i < s1 . Length ; i ++) { int x = s1 [ i ] - 'a' ; int y = s2 [ i ] - 'a' ; int px = Find ( x ); int py = Find ( y ); if ( px < py ) { p [ py ] = px ; } else { p [ px ] = py ; } } var res = new System . Text . StringBuilder (); foreach ( char c in baseStr ) { int idx = Find ( c - 'a' ); res . Append (( char )( idx + 'a' )); } return res . ToString (); } }

1class Solution {2private3  int[] p;4public5  String smallestEquivalentString(String s1, String s2, String baseStr) {6    p = new int[26];7    for (int i = 0; i < 26; ++i) {8      p[i] = i;9    }10    for (int i = 0; i < s1.length(); ++i) {11      int a = s1.charAt(i) - 'a', b = s2.charAt(i) - 'a';12      int pa = find(a), pb = find(b);13      if (pa < pb) {14        p[pb] = pa;15      } else {16        p[pa] = pb;17      }18    }19    StringBuilder sb = new StringBuilder();20    for (char a : baseStr.toCharArray()) {21      char b = (char)(find(a - 'a') + 'a');22      sb.append(b);23    }24    return sb.toString();25  }26private27  int find(int x) {28    if (p[x] != x) {29      p[x] = find(p[x]);30    }31    return p[x];32  }33}

1class Solution {2public:3  vector<int> p;4  string smallestEquivalentString(string s1, string s2, string baseStr) {5    p.resize(26);6    for (int i = 0; i < 26; ++i)7      p[i] = i;8    for (int i = 0; i < s1.size(); ++i) {9      int a = s1[i] - 'a', b = s2[i] - 'a';10      int pa = find(a), pb = find(b);11      if (pa < pb)12        p[pb] = pa;13      else14        p[pa] = pb;15    }16    string res = "";17    for (char a : baseStr) {18      char b = (char)(find(a - 'a') + 'a');19      res += b;20    }21    return res;22  }23  int find(int x) {24    if (p[x] != x)25      p[x] = find(p[x]);26    return p[x];27  }28};

1class Solution:2    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str: p = list(range(26)) def find(x): if p[x] != x: p[x] = find(p[x]) return p[x] for i in range(len(s1)): a, b = ord(s1[i]) - ord('a'), ord(s2[i]) - ord('a') pa, pb = find(a), find(b) if pa < pb: p[pb] = pa else: p[pa] = pb res = [] for a in baseStr: a = ord(a) - ord('a') res . append(chr(find(a) + ord('a'))) return '' . join(res)

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem