Count Pairs of Numbers That Become Equal After at Most One Digit Swap

You are given a list of non-negative integers nums. Two numbers form a matching pair if they are equal, or if you can make them equal by choosing one of the two numbers and swapping two of its digits once.

Return the number of index pairs (i, j) with i < j such that nums[i] and nums[j] form a matching pair.

Function Signature

def count_matching_pairs(nums: list[int]) -> int:

Rules

• A pair gets at most one swap in total, applied to only one of its two numbers. A pair that would need a swap in each number, or two swaps in the same number, does not match.
• A swap exchanges the digits at two different positions of the chosen number's usual decimal form, written without leading zeros.
• The result of a swap may start with one or more zeros. It is read as a number with those leading zeros dropped: swapping the two digits of 30 gives 03, which equals 3, so 30 and 3 form a matching pair.
• Swaps are only imagined, never applied: nums is not changed, and every pair is judged on the original values.
• Pairs are counted by index, so equal values at different indices form a pair.

Constraints

• 1 <= len(nums) <= 10000
• 0 <= nums[i] <= 1000000000
• The result is an integer from 0 to len(nums) * (len(nums) - 1) / 2 inclusive, and it is uniquely determined by the input.

Examples

Example 1

• Input: nums = [4, 123, 452, 321, 132]
• Output: 2
• Explanation: 123 and 321 match by swapping the 1 and the 3 of 123, and 123 and 132 match by swapping its 2 and 3. 321 and 132 differ in all three positions, so a single swap in either one cannot make them equal. 4 and 452 match nothing.

Example 2

• Input: nums = [30, 3, 12, 21, 12]
• Output: 4
• Explanation: The matching index pairs are (0, 1) because 30 becomes 03 = 3, (2, 3) and (3, 4) because 12 and 21 differ by one swap, and (2, 4) because the values are equal.

Example 3

• Input: nums = [100, 1, 10, 1000]
• Output: 6
• Explanation: Every pair matches. 100 can become 010 = 10 or 001 = 1, 10 can become 01 = 1, and 1000 can become 0100 = 100, 0010 = 10 or 0001 = 1.

One-Swap Digit Pairs

You are given a list of non-negative integers nums. Two numbers form a matching pair if they are equal, or if they can be made equal by picking one of the two numbers and swapping two of its digits exactly once.

Implement count_matching_pairs(nums) and return the number of index pairs (i, j) with i < j such that nums[i] and nums[j] form a matching pair.

Rules

• A pair gets at most one swap in total, applied to only one of its two numbers. A pair that would need a swap in each number, or two swaps in the same number, does not match.
• A swap exchanges the digits at two different positions of the chosen number's usual decimal form, written without leading zeros. A single-digit number (including 0) has no swap available.
• The result of a swap may start with one or more zeros. It is read as a number with those leading zeros dropped: swapping the two digits of 30 gives 03, which equals 3, so 30 and 3 form a matching pair. Likewise 1000 can become 0100 = 100, 0010 = 10 or 0001 = 1.
• Swaps are only imagined, never applied: nums is not changed, and every pair is judged on the original values. Matching is not transitive.
• Pairs are counted by index, so equal values at different indices form a pair.

Output

Return a single integer: the number of matching index pairs. The answer is uniquely determined by the input.

Constraints

• 1 <= len(nums) <= 10000
• 0 <= nums[i] <= 1000000000
• The result is an integer from 0 to len(nums) * (len(nums) - 1) / 2 inclusive (at most 49,995,000).
• Every input value and the result fit in a 32-bit signed integer (no value exceeds 2^31 - 1), so int is sufficient in Java and C++.

Example 1

Input:  nums = [4, 123, 452, 321, 132]
Output: 2

123 and 321 match by swapping the 1 and the 3 of 123, and 123 and 132 match by swapping its 2 and 3. 321 and 132 differ in all three positions, so a single swap in either one cannot make them equal. 4 and 452 match nothing.

Example 2

Input:  nums = [30, 3, 12, 21, 12]
Output: 4

The matching index pairs are (0, 1) because 30 becomes 03 = 3, (2, 3) and (3, 4) because 12 and 21 differ by one swap, and (2, 4) because the values are equal.

Hints

1. A number has at most 10 digits, so it has at most 45 single-swap results -- far fewer than the roughly 5 * 10^7 index pairs a 10000-element list can have.
2. A swap can shorten a number (leading zeros are dropped) but never lengthen it. If you look at the values in increasing order, which number of a pair is the only one that could ever need the swap?
3. Different swaps of the same number can produce the same value (for example when two equal digits are swapped), so make sure each earlier element is counted at most once per later element.

Approach

Sort a copy of nums in increasing order and scan it while keeping a hash map counts from each value already scanned to how many times it has appeared. For the current value x, build the set R(x) containing x itself and every value obtained by swapping two positions of its decimal string that hold different digits (reading the result with leading zeros dropped). Add counts[v] for every v in R(x) to the answer, then increment counts[x].

Why every matching pair is counted exactly once: take a pair whose values are a <= b in sorted order, so a is scanned first. If a == b, a is in R(b). Otherwise one swap turns one of them into the other. A swap never adds digits, so a value reachable from b has at most as many digits as b; the only way b can come from a swap of a is if b has at most as many digits as a, and since a < b it has at least as many, so they have the same length and the swap did not create a leading zero. Two equal-length numbers that differ by one transposition are each a transposition of the other, so a is in R(b) in that case too. Swaps in b that shorten it (e.g. 30 -> 03 = 3) put the shorter a directly in R(b). Hence every matching pair is found when its later element is scanned, and using a set for R(b) ensures that an earlier element is added once even if several swaps reach its value. Non-matching pairs are never counted because R(b) contains only values one swap (or zero swaps) away from b.

Each value has at most 10 digits, so R(x) has at most 46 entries, and the total work is dominated by sorting plus n * 45 string swaps and hash lookups. The answer is at most 10000 * 9999 / 2 = 49,995,000, and every swapped value is at most 1000000000, so 32-bit integers suffice in every language.

• Time complexity: O(n log n + n * D^2), where D <= 10 is the number of digits
• Space complexity: O(n)