Count almost equal pairs i

Array Hash Table Sorting Counting Enumeration

38.2% acceptance

Feb 25, 2026

159

You are given an array nums of positive integers. Two integers x and y are almost equal if you can swap any two digits in one of them to make them equal (at most once). Return the number of pairs i < j where nums[i] and nums[j] are almost equal.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_pairs(nums: Vec<i32>) -> i32 {
    let n = nums.len();
    let mut ans = 0i32;
    for i in 0..n {
      for j in (i + 1)..n {
        if Self::almost_equal(nums[i], nums[j]) {
          ans += 1;
        }
      }
    }
    ans
  }

  fn almost_equal(x: i32, y: i32) -> bool {
    if x == y {
      return true;
    }
    // Try swapping two digits in x to get y
    let xs: Vec<u8> = x.to_string().bytes().collect();
    let ys: Vec<u8> = y.to_string().bytes().collect();
    if Self::can_swap_to(&xs, y) {
      return true;
    }
    Self::can_swap_to(&ys, x)
  }

  fn can_swap_to(digits: &[u8], target: i32) -> bool {
    let d = digits.len();
    let mut buf = digits.to_vec();
    for i in 0..d {
      for j in (i + 1)..d {
        buf.swap(i, j);
        // Parse as integer (leading zeros reduce the number)
        let val: i32 = std::str::from_utf8(&buf).unwrap().parse().unwrap();
        if val == target {
          return true;
        }
        buf.swap(i, j);
      }
    }
    false
  }
}