Smallest string with swaps

Array Hash Table String Depth-First Search Breadth-First Search Union-Find Sorting

60.4% acceptance

Feb 25, 2026

3899

165

You are given a string s, and an array of pairs of indices in the string pairs where pairs[i] = [a, b] indicates 2 indices(0-indexed) of the string. You can swap the characters at any pair of indices in the given pairs any number of times. Return the lexicographically smallest string that s can be changed to after using the swaps.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn smallest_string_with_swaps(s: String, pairs: Vec<Vec<i32>>) -> String {
    let n = s.len();
    let mut parent: Vec<usize> = (0..n).collect();

    fn find(parent: &mut Vec<usize>, x: usize) -> usize {
      if parent[x] != x {
        parent[x] = find(parent, parent[x]);
      }
      parent[x]
    }

    fn union(parent: &mut Vec<usize>, x: usize, y: usize) {
      let px = find(parent, x);
      let py = find(parent, y);
      if px != py {
        parent[px] = py;
      }
    }

    for pair in &pairs {
      union(&mut parent, pair[0] as usize, pair[1] as usize);
    }

    let chars: Vec<char> = s.chars().collect();
    let mut groups: std::collections::HashMap<usize, Vec<usize>> = std::collections::HashMap::new();
    for i in 0..n {
      let root = find(&mut parent, i);
      groups.entry(root).or_default().push(i);
    }

    let mut result: Vec<char> = chars.clone();
    for (_, indices) in &mut groups {
      indices.sort();
      let mut char_group: Vec<char> = indices.iter().map(|&i| chars[i]).collect();
      char_group.sort();
      for (j, &idx) in indices.iter().enumerate() {
        result[idx] = char_group[j];
      }
    }
    result.into_iter().collect()
  }
}