Count Pairs of Numbers That Become Equal After at Most One Digit Swap
Company: Capital One
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Technical Screen
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
```python
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`.
Overview: Given a list of integers, count the index pairs whose values are equal or become equal after swapping two digits inside one of the two numbers, where leading zeros created by a swap are dropped. It tests digit manipulation, careful handling of numbers with different lengths, and hashing to avoid comparing every pair.
