Lexicographically smallest equivalent string

String Union-Find

81.1% acceptance

Feb 25, 2026

2874

186

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.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_equivalent_string(s1: String, s2: String, base_str: String) -> String {
    let mut parent: Vec<usize> = (0..26).collect();
    fn find(p: &mut Vec<usize>, x: usize) -> usize {
      if p[x] != x { p[x] = find(p, p[x]); }
      p[x]
    }
    for (a, b) in s1.bytes().zip(s2.bytes()) {
      let (ra, rb) = (find(&mut parent, (a - b'a') as usize), find(&mut parent, (b - b'a') as usize));
      if ra != rb { parent[ra.max(rb)] = ra.min(rb); } // smaller letter becomes root
    }
    base_str.bytes().map(|c| {
      let r = find(&mut parent, (c - b'a') as usize);
      (b'a' + r as u8) as char
    }).collect()
  }
}