<p><strong>Attention</strong>: In this version, the number of operations that can be performed, has been increased to <strong>twice</strong>.<!-- notionvc: 278e7cb2-3b05-42fa-8ae9-65f5fd6f7585 --></p>

<p>You are given an array <code>nums</code> consisting of positive integers.</p>

<p>We call two integers <code>x</code> and <code>y</code> <strong>almost equal</strong> if both integers can become equal after performing the following operation <strong>at most <u>twice</u></strong>:</p>

<ul>
	<li>Choose <strong>either</strong> <code>x</code> or <code>y</code> and swap any two digits within the chosen number.</li>
</ul>

<p>Return the number of indices <code>i</code> and <code>j</code> in <code>nums</code> where <code>i &lt; j</code> such that <code>nums[i]</code> and <code>nums[j]</code> are <strong>almost equal</strong>.</p>

<p><strong>Note</strong> that it is allowed for an integer to have leading zeros after performing an operation.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1023,2310,2130,213]</span></p>

<p><strong>Output:</strong> <span class="example-io">4</span></p>

<p><strong>Explanation:</strong></p>

<p>The almost equal pairs of elements are:</p>

<ul>
	<li>1023 and 2310. By swapping the digits 1 and 2, and then the digits 0 and 3 in 1023, you get 2310.</li>
	<li>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.</li>
	<li>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.</li>
	<li>2310 and 2130. By swapping the digits 3 and 1 in 2310, you get 2130.</li>
</ul>
</div>

<p><strong class="example">Example 2:</strong></p>

<div class="example-block">
<p><strong>Input:</strong> <span class="example-io">nums = [1,10,100]</span></p>

<p><strong>Output:</strong> <span class="example-io">3</span></p>

<p><strong>Explanation:</strong></p>

<p>The almost equal pairs of elements are:</p>

<ul>
	<li>1 and 10. By swapping the digits 1 and 0 in 10, you get 01 which is 1.</li>
	<li>1 and 100. By swapping the second 0 with the digit 1 in 100, you get 001, which is 1.</li>
	<li>10 and 100. By swapping the first 0 with the digit 1 in 100, you get 010, which is 10.</li>
</ul>
</div>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 5000</code></li>
	<li><code>1 &lt;= nums[i] &lt; 10<sup>7</sup></code></li>
</ul>

from typing import List, DefaultDict, Set
from collections import defaultdict, Counter
from itertools import combinations

class Solution:
    def countPairs(self, nums: List[int]) -> int:

        # 生成候選字串的函數，返回所有可能的通過交換兩個不同位置字符後的字串列表
        def generate_candidates(s: str) -> List[str]:
            x = list(s)
            candidates = []
            for i in range(len(x)):
                for j in range(i + 1, len(x)):
                    if x[i] == x[j]:
                        continue  # 如果字符相同則跳過
                    x[i], x[j] = x[j], x[i]  # 暫時交換字符
                    candidates.append(''.join(x))  # 加入候選字串列表
                    x[i], x[j] = x[j], x[i]  # 恢復原字符順序
            return candidates


        # 初始化答案為 0
        ans = 0
        
        # 將 nums 中的數字轉換成統一長度的字串形式
        max_len = max(len(str(x)) for x in nums)
        nums = [str(x).zfill(max_len) for x in nums]
        
        # 統計每個字串的出現次數
        freq = Counter(nums)
        
        # 初始化一個字典來記錄每個字串和其所有候選字串
        connects = defaultdict(list)
        

        # 遍歷每個字串及其出現次數
        for s, cnt in freq.items():
            # 計算 0 次交換的情況，直接計算相同字串之間的配對數量
            ans += cnt * (cnt - 1) // 2
            
            # 將字串本身加入到 connects 中
            connects[s].append(s)
            
            # 生成 1 次交換的候選字串，並加入 connects 中
            # (候選字串 cand 不一定會出現在 nums 中，但是 s 一定在 nums 中)
            # (拿 cand 當作 group key，可以讓 group 中的字串都在 2 次交換以內)
            for cand in generate_candidates(s):
                connects[cand].append(s)
        
        # 使用一個集合來避免重複計算配對
        pairs = set()
        
        # 遍歷所有可能的候選字串配對
        for cand, neighbours in connects.items():
            # 產生 neighbours 中所有的 pair (y1, y2)
            # 
            # 備註： 在這裡其實 cand 用不到，主要是看 neighbors 中的字串
            #       (y1 -> cand) 距離 <= 1, (y2 -> cand) 距離 <= 1
            #       所以 (y1 -> y2) 距離 <= 2
            for y1, y2 in combinations(neighbours, 2):
                # 只計算還沒算過的配對
                if (y1, y2) not in pairs:
                    pairs.add((y1, y2))  # 記錄已計算過的配對
                    # 計算有效的配對數量，並累加到結果中
                    ans += freq[y1] * freq[y2]
        
        return ans

43926