Lexicographically Smallest Equivalent String

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.

Examples

Example 1:

1
2
3
4
5
6
7


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:

1
2
3
4
5
6


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:

1
2
3
4
5


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".

Solution

Method 1 – Union-Find (Disjoint Set Union)

Intuition

The key idea is to use union-find to group all equivalent characters. For each character, its representative in the union-find structure is the lexicographically smallest character in its equivalence class. For each character in baseStr, replace it with the smallest equivalent character.

Approach

Initialize a parent array for all 26 lowercase letters.
For each pair (s1[i], s2[i]), union their sets, always keeping the smaller character as the parent.
For each character in baseStr, find its representative (smallest equivalent character) and build the result string.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        vector<int> par(26);
        iota(par.begin(), par.end(), 0);
        auto find = [&](int x) {
            while (par[x] != x) x = par[x] = par[par[x]];
            return x;
        };
        for (int i = 0; i < s1.size(); ++i) {
            int a = find(s1[i] - 'a'), b = find(s2[i] - 'a');
            if (a != b) par[max(a, b)] = min(a, b);
        }
        string ans;
        for (char c : baseStr) ans += (char)(find(c - 'a') + 'a');
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17


func smallestEquivalentString(s1, s2, baseStr string) string {
    par := make([]int, 26)
    for i := range par { par[i] = i }
    var find func(int) int
    find = func(x int) int { if par[x] != x { par[x] = find(par[x]) }; return par[x] }
    for i := 0; i < len(s1); i++ {
        a, b := find(int(s1[i]-'a')), find(int(s2[i]-'a'))
        if a != b {
            if a < b { par[b] = a } else { par[a] = b }
        }
    }
    ans := make([]byte, len(baseStr))
    for i := 0; i < len(baseStr); i++ {
        ans[i] = byte(find(int(baseStr[i]-'a')) + 'a')
    }
    return string(ans)
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution {
    public String smallestEquivalentString(String s1, String s2, String baseStr) {
        int[] par = new int[26];
        for (int i = 0; i < 26; i++) par[i] = i;
        for (int i = 0; i < s1.length(); i++) {
            int a = find(par, s1.charAt(i) - 'a');
            int b = find(par, s2.charAt(i) - 'a');
            if (a != b) par[Math.max(a, b)] = Math.min(a, b);
        }
        StringBuilder ans = new StringBuilder();
        for (char c : baseStr.toCharArray()) ans.append((char)(find(par, c - 'a') + 'a'));
        return ans.toString();
    }
    private int find(int[] par, int x) {
        if (par[x] != x) par[x] = find(par, par[x]);
        return par[x];
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution {
    fun smallestEquivalentString(s1: String, s2: String, baseStr: String): String {
        val par = IntArray(26) { it }
        fun find(x: Int): Int = if (par[x] == x) x else { par[x] = find(par[x]); par[x] }
        for (i in s1.indices) {
            val a = find(s1[i] - 'a')
            val b = find(s2[i] - 'a')
            if (a != b) par[maxOf(a, b)] = minOf(a, b)
        }
        return baseStr.map { (find(it - 'a') + 'a'.code).toChar() }.joinToString("")
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def smallestEquivalentString(self, s1: str, s2: str, baseStr: str) -> str:
        par = list(range(26))
        def find(x: int) -> int:
            if par[x] != x:
                par[x] = find(par[x])
            return par[x]
        for a, b in zip(s1, s2):
            pa, pb = find(ord(a)-97), find(ord(b)-97)
            if pa != pb:
                par[max(pa, pb)] = min(pa, pb)
        return ''.join(chr(find(ord(c)-97)+97) for c in baseStr)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


impl Solution {
    pub fn smallest_equivalent_string(s1: String, s2: String, base_str: String) -> String {
        let mut par: Vec<_> = (0..26).collect();
        fn find(par: &mut Vec<usize>, x: usize) -> usize {
            if par[x] != x { par[x] = find(par, par[x]); }
            par[x]
        }
        let s1 = s1.as_bytes();
        let s2 = s2.as_bytes();
        for i in 0..s1.len() {
            let a = find(&mut par, (s1[i] - b'a') as usize);
            let b = find(&mut par, (s2[i] - b'a') as usize);
            if a != b {
                par[a.max(b)] = a.min(b);
            }
        }
        base_str.bytes().map(|c| (find(&mut par, (c - b'a') as usize) as u8 + b'a') as char).collect()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


class Solution {
    smallestEquivalentString(s1: string, s2: string, baseStr: string): string {
        const par = Array.from({length: 26}, (_, i) => i);
        const find = (x: number): number => par[x] === x ? x : (par[x] = find(par[x]));
        for (let i = 0; i < s1.length; i++) {
            const a = find(s1.charCodeAt(i) - 97), b = find(s2.charCodeAt(i) - 97);
            if (a !== b) par[Math.max(a, b)] = Math.min(a, b);
        }
        return Array.from(baseStr, c => String.fromCharCode(find(c.charCodeAt(0) - 97) + 97)).join("");
    }
}

Complexity

⏰ Time complexity: O(n + m), where n is the length of s1/s2 and m is the length of baseStr; union-find operations are nearly constant time.
🧺 Space complexity: O(1), since the parent array is fixed size (26).

Problem#

Examples#

Solution#

Method 1 – Union-Find (Disjoint Set Union)#

Intuition#

Approach#

Code#

Complexity#