Problem

Attention : In this version, the number of operations that can be performed, has been increased to twice.

You are given an array nums consisting of positive integers.

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

  • 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
12
13


Input: nums = [1023,2310,2130,213]

Output: 4

Explanation:

The almost equal pairs of elements are:

  * 1023 and 2310. By swapping the digits 1 and 2, and then the digits 0 and 3 in 1023, you get 2310.
  * 1023 and 213. By swapping the digits 1 and 0, and then the digits 1 and 2 in 1023, you get 0213, which is 213.
  * 2310 and 213. By swapping the digits 2 and 0, and then the digits 3 and 2 in 2310, you get 0213, which is 213.
  * 2310 and 2130. By swapping the digits 3 and 1 in 2310, you get 2130.

Example 2

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


Input: nums = [1,10,100]

Output: 3

Explanation:

The almost equal pairs of elements are:

  * 1 and 10. By swapping the digits 1 and 0 in 10, you get 01 which is 1.
  * 1 and 100. By swapping the second 0 with the digit 1 in 100, you get 001, which is 1.
  * 10 and 100. By swapping the first 0 with the digit 1 in 100, you get 010, which is 10.

Constraints

  • 2 <= nums.length <= 5000
  • 1 <= nums[i] < 10^7

Solution

Method 1 – Hashing and Two Swaps Enumeration 1

Intuition

Since we can swap any two digits up to two times in either number, two numbers are almost equal if their digits can be rearranged to match with at most two swaps. For each number, we can generate all numbers reachable by up to two swaps and count how many times each appears in the array. For each pair, if their swapped forms match, they are almost equal.

Approach

  1. For each number in nums, generate all possible numbers by performing up to two swaps (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
25
26
27
28
29
30
31

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;
            int n = s.size();
            for (int a = 0; a < n; ++a) {
                for (int b = a; b < n; ++b) {
                    swap(s[a], s[b]);
                    for (int c = 0; c < n; ++c) {
                        for (int d = c; d < n; ++d) {
                            swap(s[c], s[d]);
                            int v = stoi(s);
                            if (!seen.count(v)) {
                                ans += freq[v] - (v == nums[i]);
                                seen.insert(v);
                            }
                            swap(s[c], s[d]);
                        }
                    }
                    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
28
29
30
31
32
33
34

func countAlmostEqualPairs(nums []int) int {
    freq := map[int]int{}
    for _, x := range nums {
        freq[x]++
    }
    ans := 0
    for _, x := range nums {
        s := []byte(strconv.Itoa(x))
        seen := map[int]bool{}
        n := len(s)
        for a := 0; a < n; a++ {
            for b := a; b < n; b++ {
                s[a], s[b] = s[b], s[a]
                for c := 0; c < n; c++ {
                    for d := c; d < n; d++ {
                        s[c], s[d] = s[d], s[c]
                        v, _ := strconv.Atoi(string(s))
                        if !seen[v] {
                            cnt := freq[v]
                            if v == x {
                                cnt--
                            }
                            ans += cnt
                            seen[v] = true
                        }
                        s[c], s[d] = s[d], s[c]
                    }
                }
                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
27
28
29
30

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<>();
            int n = s.length;
            for (int a = 0; a < n; ++a) {
                for (int b = a; b < n; ++b) {
                    char tmp = s[a]; s[a] = s[b]; s[b] = tmp;
                    for (int c = 0; c < n; ++c) {
                        for (int d = c; d < n; ++d) {
                            char tmp2 = s[c]; s[c] = s[d]; s[d] = tmp2;
                            int v = Integer.parseInt(new String(s));
                            if (!seen.contains(v)) {
                                ans += freq.getOrDefault(v, 0) - (v == nums[i] ? 1 : 0);
                                seen.add(v);
                            }
                            tmp2 = s[c]; s[c] = s[d]; s[d] = tmp2;
                        }
                    }
                    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
24
25
26
27
28
29
30

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>()
            val n = s.size
            for (a in 0 until n) {
                for (b in a until n) {
                    s[a] = s[b].also { s[b] = s[a] }
                    for (c in 0 until n) {
                        for (d in c until n) {
                            s[c] = s[d].also { s[d] = s[c] }
                            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[c] = s[d].also { s[d] = s[c] }
                        }
                    }
                    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
18
19
20
21
22

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()
            n = len(s)
            for a in range(n):
                for b in range(a, n):
                    s[a], s[b] = s[b], s[a]
                    for c in range(n):
                        for d in range(c, n):
                            s[c], s[d] = s[d], s[c]
                            v = int(''.join(s))
                            if v not in seen:
                                ans += freq[v] - (v == x)
                                seen.add(v)
                            s[c], s[d] = s[d], s[c]
                    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
27
28
29
30
31
32
33

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 n = s.len();
            let mut seen = HashSet::new();
            for a in 0..n {
                for b in a..n {
                    let mut t = s.clone();
                    t.swap(a, b);
                    for c in 0..n {
                        for d in c..n {
                            let mut u = t.clone();
                            u.swap(c, d);
                            let v: i32 = u.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
24
25
26
27
28
29
30

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 n = s.length;
            const seen = new Set<number>();
            for (let a = 0; a < n; ++a) {
                for (let b = a; b < n; ++b) {
                    [s[a], s[b]] = [s[b], s[a]];
                    for (let c = 0; c < n; ++c) {
                        for (let d = c; d < n; ++d) {
                            [s[c], s[d]] = [s[d], s[c]];
                            const v = parseInt(s.join(''));
                            if (!seen.has(v)) {
                                ans += (freq.get(v) ?? 0) - (v === nums[i] ? 1 : 0);
                                seen.add(v);
                            }
                            [s[c], s[d]] = [s[d], s[c]];
                        }
                    }
                    [s[a], s[b]] = [s[b], s[a]];
                }
            }
        }
        return Math.floor(ans / 2);
    }
}

Complexity

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