Problem

You are given an array nums consisting of positive integers.

We call two integers x and y in this problem almost equal if both integers can become equal after performing the following operation at most once :

  • Choose either x or y and swap any two digits within the chosen number.

Return the number of indices i and j in nums where i < j such that nums[i] and nums[j] are almost equal.

Note that it is allowed for an integer to have leading zeros after performing an operation.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


Input: nums = [3,12,30,17,21]

Output: 2

Explanation:

The almost equal pairs of elements are:

  * 3 and 30. By swapping 3 and 0 in 30, you get 3.
  * 12 and 21. By swapping 1 and 2 in 12, you get 21.

Example 2

1
2
3
4
5
6
7
8


Input: nums = [1,1,1,1,1]

Output: 10

Explanation:

Every two elements in the array are almost equal.

Example 3

1
2
3
4
5
6
7
8


Input: nums = [123,231]

Output: 0

Explanation:

We cannot swap any two digits of 123 or 231 to reach the other.

Constraints

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 10^6

Solution

Method 1 – Hashing and Digit Swapping 1

Intuition

For two numbers to be almost equal, one should be able to reach the other by swapping any two digits in one of them. For each number, we can generate all possible numbers by swapping any two digits (including itself), and count how many times each number appears. For each pair, if their swapped forms match, they are almost equal.

Approach

  1. For each number in nums, generate all possible numbers by swapping any two digits (including itself).
  2. Use a hash map to count the frequency of each number in nums.
  3. For each number, for each of its swapped forms, add the count of that form (excluding itself if i == j).
  4. Since each pair is counted twice, divide the total by 2.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
public:
    int countAlmostEqualPairs(vector<int>& nums) {
        unordered_map<int, int> freq;
        for (int x : nums) freq[x]++;
        int ans = 0;
        for (int i = 0; i < nums.size(); ++i) {
            string s = to_string(nums[i]);
            set<int> seen;
            for (int a = 0; a < s.size(); ++a) {
                for (int b = a; b < s.size(); ++b) {
                    swap(s[a], s[b]);
                    int v = stoi(s);
                    if (!seen.count(v)) {
                        ans += freq[v] - (v == nums[i]);
                        seen.insert(v);
                    }
                    swap(s[a], s[b]);
                }
            }
        }
        return ans / 2;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func countAlmostEqualPairs(nums []int) int {
    freq := map[int]int{}
    for _, x := range nums {
        freq[x]++
    }
    ans := 0
    for i, x := range nums {
        s := []byte(strconv.Itoa(x))
        seen := map[int]bool{}
        for a := 0; a < len(s); a++ {
            for b := a; b < len(s); b++ {
                s[a], s[b] = s[b], s[a]
                v, _ := strconv.Atoi(string(s))
                if !seen[v] {
                    cnt := freq[v]
                    if v == x {
                        cnt--
                    }
                    ans += cnt
                    seen[v] = true
                }
                s[a], s[b] = s[b], s[a]
            }
        }
    }
    return ans / 2
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    public int countAlmostEqualPairs(int[] nums) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int x : nums) freq.put(x, freq.getOrDefault(x, 0) + 1);
        int ans = 0;
        for (int i = 0; i < nums.length; ++i) {
            char[] s = String.valueOf(nums[i]).toCharArray();
            Set<Integer> seen = new HashSet<>();
            for (int a = 0; a < s.length; ++a) {
                for (int b = a; b < s.length; ++b) {
                    char tmp = s[a]; s[a] = s[b]; s[b] = tmp;
                    int v = Integer.parseInt(new String(s));
                    if (!seen.contains(v)) {
                        ans += freq.getOrDefault(v, 0) - (v == nums[i] ? 1 : 0);
                        seen.add(v);
                    }
                    tmp = s[a]; s[a] = s[b]; s[b] = tmp;
                }
            }
        }
        return ans / 2;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    fun countAlmostEqualPairs(nums: IntArray): Int {
        val freq = mutableMapOf<Int, Int>()
        for (x in nums) freq[x] = freq.getOrDefault(x, 0) + 1
        var ans = 0
        for (i in nums.indices) {
            val s = nums[i].toString().toCharArray()
            val seen = mutableSetOf<Int>()
            for (a in s.indices) {
                for (b in a until s.size) {
                    s[a] = s[b].also { s[b] = s[a] }
                    val v = String(s).toInt()
                    if (v !in seen) {
                        ans += freq.getOrDefault(v, 0) - if (v == nums[i]) 1 else 0
                        seen.add(v)
                    }
                    s[a] = s[b].also { s[b] = s[a] }
                }
            }
        }
        return ans / 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def countAlmostEqualPairs(self, nums: list[int]) -> int:
        from collections import Counter
        freq = Counter(nums)
        ans = 0
        for i, x in enumerate(nums):
            s = list(str(x))
            seen = set()
            for a in range(len(s)):
                for b in range(a, len(s)):
                    s[a], s[b] = s[b], s[a]
                    v = int(''.join(s))
                    if v not in seen:
                        ans += freq[v] - (v == x)
                        seen.add(v)
                    s[a], s[b] = s[b], s[a]
        return ans // 2
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

impl Solution {
    pub fn count_almost_equal_pairs(nums: Vec<i32>) -> i32 {
        use std::collections::{HashMap, HashSet};
        let mut freq = HashMap::new();
        for &x in &nums {
            *freq.entry(x).or_insert(0) += 1;
        }
        let mut ans = 0;
        for &x in &nums {
            let s: Vec<char> = x.to_string().chars().collect();
            let mut seen = HashSet::new();
            for a in 0..s.len() {
                for b in a..s.len() {
                    let mut t = s.clone();
                    t.swap(a, b);
                    let v: i32 = t.iter().collect::<String>().parse().unwrap();
                    if !seen.contains(&v) {
                        ans += freq.get(&v).unwrap_or(&0) - if v == x { 1 } else { 0 };
                        seen.insert(v);
                    }
                }
            }
        }
        ans / 2
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
    countAlmostEqualPairs(nums: number[]): number {
        const freq = new Map<number, number>();
        for (const x of nums) freq.set(x, (freq.get(x) ?? 0) + 1);
        let ans = 0;
        for (let i = 0; i < nums.length; ++i) {
            const s = nums[i].toString().split('');
            const seen = new Set<number>();
            for (let a = 0; a < s.length; ++a) {
                for (let b = a; b < s.length; ++b) {
                    [s[a], s[b]] = [s[b], s[a]];
                    const v = parseInt(s.join(''));
                    if (!seen.has(v)) {
                        ans += (freq.get(v) ?? 0) - (v === nums[i] ? 1 : 0);
                        seen.add(v);
                    }
                    [s[a], s[b]] = [s[b], s[a]];
                }
            }
        }
        return Math.floor(ans / 2);
    }
}

Complexity

  • ⏰ Time complexity: O(n * d^2), where n is the length of nums and d is the maximum number of digits in any number. For each number, we try all digit swaps.
  • 🧺 Space complexity: O(n), for the frequency map and sets.