Counting Almost Equal Pairs with Double Swap in a List | coderkb
Intuition\nTo count pairs of integers in an array that become equal when two digits are swapped at most twice, we can generate all possible numbers by performin
## Intuition\nTo count pairs of integers in an array that become equal when two digits are swapped at most twice, we can generate all possible numbers by performing up to two swaps on each number\'s digits. We then check how many of these generated numbers have already been seen in the array.\n\n## Approach\n1. **Digit Standardization:**\n   - Convert each integer in the array to a standardized string format with leading zeros to ensure consistent digit length.\n\n2. **Generate Possible Numbers:**\n   - For each number, generate all possible numbers that can be obtained by performing up to two swaps on its digits.\n   - Use a `set` to store unique possibilities for each number.\n\n3. **Counting Valid Pairs:**\n   - Traverse the array, and for each number, check if any of its possible swapped forms have been seen before using a hash map.\n   - If so, increment the count by the frequency of the matched form.\n   - Finally, update the hash map with the current number\'s standardized form.\n\n## Complexity\n- **Time complexity:** $$O(n \\times d^4)$$, where `n` is the number of integers in the array and `d` is the number of digits in the largest integer. The complexity is due to the nested loops for generating all possible swap combinations.\n- **Space complexity:** $$O(n \\times d^2)$$, where `n` is the number of integers, and `d^2` accounts for the storage of possible swaps for each number.\n\n## Code\n```cpp\nclass Solution {\n    string makeDigit(int num, int digits) {\n        string numStr = to_string(num);\n    \n        // If the string length is less than the desired size, prepend zeros\n        if (numStr.length() < digits) {\n            numStr.insert(numStr.begin(), digits - numStr.length(), \'0\');\n        }\n        \n        return numStr;\n    }\n\n    unordered_set<string> makeSwapChanges(int num, int digits) {\n        string s = makeDigit(num, digits);\n        unordered_set<string> poss;\n        poss.insert(s);\n        \n        for(int i = 0; i < digits; ++i) {\n            for(int j = i + 1; j < digits; ++j) {\n                if(s[i] != s[j]) {\n                    swap(s[i], s[j]);\n                    poss.insert(s);\n                    for(int i1 = 0; i1 < digits; ++i1) {\n                        for(int j1 = 0; j1 < digits; ++j1) {\n                            if(i == i1 && j == j1) continue;\n\n                            if(s[i1] != s[j1]) {\n                                swap(s[i1], s[j1]);\n                                poss.insert(s);\n                                swap(s[j1], s[i1]);\n                            }\n                        }\n                    }\n                    swap(s[i], s[j]);\n                }\n            }\n        }\n        return poss;\n    }\n\npublic:\n    int countPairs(vector<int>& nums) {\n        int n = nums.size();\n\n        int mx = 0;\n        for(int num : nums) mx = max(mx, num);\n\n        int digits = to_string(mx).size();\n\n        unordered_map<string, int> mp;\n        mp[makeDigit(nums[0], digits)]++;\n        int ans = 0;\n        for(int i = 1; i < n; ++i) {\n            for(const auto& s : makeSwapChanges(nums[i], digits)) {\n                if(mp.find(s) != mp.end()) {\n                    ans += mp[s];\n                }\n            }\n\n            mp[makeDigit(nums[i], digits)]++;\n        }\n\n        return ans;\n    }\n};\n```\n\nThis solution effectively handles counting "almost equal" pairs by leveraging digit manipulation and hashing, ensuring that the problem is tackled within acceptable time limits for the given constraints.
['C++']