# Lexicographically Smallest Equivalent String
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/lexicographically-smallest-equivalent-string)
Canonical: https://scaleengineer.com/dsa/problems/lexicographically-smallest-equivalent-string
**Algorithms:** [Union Find](https://scaleengineer.com/algorithms/union-find)
**Data structures:** String
**Companies:** [Cloudera](https://scaleengineer.com/companies/cloudera)
---
## Problem
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
## Graph Traversal (DFS/BFS)
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.
**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).
**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).
### Explanation
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.

1.  **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]`.

2.  **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.

3.  **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.

```java
import java.util.*;

class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        // Step 1: Build the graph using an array of lists
        List<Integer>[] adj = new ArrayList[26];
        for (int i = 0; i < 26; i++) {
            adj[i] = new ArrayList<>();
        }
        for (int i = 0; i < s1.length(); i++) {
            int u = s1.charAt(i) - 'a';
            int v = s2.charAt(i) - 'a';
            adj[u].add(v);
            adj[v].add(u);
        }

        // Step 2: Find components and their representatives
        int[] mapping = new int[26];
        boolean[] visited = new boolean[26];

        for (int i = 0; i < 26; i++) {
            if (!visited[i]) {
                List<Integer> component = new ArrayList<>();
                int minCharIndex = i;
                
                Stack<Integer> stack = new Stack<>();
                stack.push(i);
                visited[i] = true;
                
                while (!stack.isEmpty()) {
                    int u = stack.pop();
                    component.add(u);
                    minCharIndex = Math.min(minCharIndex, u);
                    
                    for (int v : adj[u]) {
                        if (!visited[v]) {
                            visited[v] = true;
                            stack.push(v);
                        }
                    }
                }
                
                for (int nodeIndex : component) {
                    mapping[nodeIndex] = minCharIndex;
                }
            }
        }

        // Step 3: Build the result string
        StringBuilder result = new StringBuilder();
        for (char c : baseStr.toCharArray()) {
            result.append((char) ('a' + mapping[c - 'a']));
        }

        return result.toString();
    }
}
```
### 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`.

## Union-Find (Disjoint Set Union)
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.
**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).
**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.
### Explanation
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`).

1.  **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.

2.  **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.

3.  **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.

4.  **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.

```java
class Solution {
    private int[] parent;

    // Find operation with path compression
    private int find(int i) {
        if (parent[i] == i) {
            return i;
        }
        return parent[i] = find(parent[i]);
    }

    // Union operation
    private void union(int i, int j) {
        int rootI = find(i);
        int rootJ = find(j);
        if (rootI != rootJ) {
            // Merge the set with the larger representative into the one with the smaller one
            if (rootI < rootJ) {
                parent[rootJ] = rootI;
            } else {
                parent[rootI] = rootJ;
            }
        }
    }

    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        // Step 1: Initialize Union-Find structure
        parent = new int[26];
        for (int i = 0; i < 26; i++) {
            parent[i] = i;
        }

        // Step 2: Process equivalences by uniting sets
        for (int i = 0; i < s1.length(); i++) {
            union(s1.charAt(i) - 'a', s2.charAt(i) - 'a');
        }

        // Step 3: Build the result string
        StringBuilder result = new StringBuilder();
        for (char c : baseStr.toCharArray()) {
            result.append((char) ('a' + find(c - 'a')));
        }

        return result.toString();
    }
}
```
### 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`.

# Solutions
### CSharp

```csharp
public 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 (); } }
```

### Java

```java
class Solution {
private
  int[] p;
public
  String smallestEquivalentString(String s1, String s2, String baseStr) {
    p = new int[26];
    for (int i = 0; i < 26; ++i) {
      p[i] = i;
    }
    for (int i = 0; i < s1.length(); ++i) {
      int a = s1.charAt(i) - 'a', b = s2.charAt(i) - 'a';
      int pa = find(a), pb = find(b);
      if (pa < pb) {
        p[pb] = pa;
      } else {
        p[pa] = pb;
      }
    }
    StringBuilder sb = new StringBuilder();
    for (char a : baseStr.toCharArray()) {
      char b = (char)(find(a - 'a') + 'a');
      sb.append(b);
    }
    return sb.toString();
  }
private
  int find(int x) {
    if (p[x] != x) {
      p[x] = find(p[x]);
    }
    return p[x];
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> p;
  string smallestEquivalentString(string s1, string s2, string baseStr) {
    p.resize(26);
    for (int i = 0; i < 26; ++i)
      p[i] = i;
    for (int i = 0; i < s1.size(); ++i) {
      int a = s1[i] - 'a', b = s2[i] - 'a';
      int pa = find(a), pb = find(b);
      if (pa < pb)
        p[pb] = pa;
      else
        p[pa] = pb;
    }
    string res = "";
    for (char a : baseStr) {
      char b = (char)(find(a - 'a') + 'a');
      res += b;
    }
    return res;
  }
  int find(int x) {
    if (p[x] != x)
      p[x] = find(p[x]);
    return p[x];
  }
};

```

### Python

```python
class Solution:
    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)

```