O(N^2) -> O(N * D^4) | Brute force digits diff comparison in Java (barely passes time constraints)
Intuition\n Describe your first thoughts on how to solve this problem. \n\nSimilarly to 3265. Count Almost Equal Pairs I, we can check all pairs for almost-equa
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\nSimilarly to [3265. Count Almost Equal Pairs I](/problems/count-almost-equal-pairs-i/), we can check all pairs for almost-equality.\n\nTo keep equlality check fast we want to test only numbers with less than 4 different digits.\n\n**UPD**: fellow C++ users report getting TLE on the same code in case of multiple vector allocations during equality check. A better time complexity is needed to safely pass all tests.\n\n**UPD**: also posted the suggested in hints hash-table version below. It passes all test cases 3 times faster.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n\nFor any pair of numbers `a` and `b` find the first 4 mismatching digits, keep the unchecked head (or tail) of the numbers as is.\n\nFor the number of differences decide if swaps are possible:\n- `0` differences - no need to swap any digits, return `true`\n- `1` - impossible to swap any pair and get the same number\n- `2`/`3` - possible if the digits match in any order\n- `4` - possble if the mismatched digits match in pairs like in `1234` and `2143`, for `1234` and `2341` 2 swaps aren\'t enough though\n- `5+` - impossible\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(N^2)$$ - 2 nested loops over the given array; Equality check is done in $$O(log10(max(nums)))$$ which is limited by 10 iterations for any integer, 4 elements diff array sorting and check takes constant time as well.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(1)$$\n\n# Code - O(N^2)\n```java []\nclass Solution {\n    public int countPairs(int[] nums) {\n        int n = nums.length;\n        int result = 0;\n        for (int i = 0; i < n; i++) {\n            for (int j = i+1; j < n; j++) {\n                result += almostEqual(nums[i], nums[j]) ? 1 : 0;\n            }\n        }\n        return result;\n    }\n\n    private boolean almostEqual(int a, int b) {\n        int found = 0;\n        // first 4 different digits for a and b\n        int[] ad = new int[4];\n        int[] bd = new int[4];\n        while (a > 0 || b > 0) {\n            if (a%10 != b%10) {\n                ad[found] = a%10;\n                bd[found] = b%10;\n                found++;\n            }\n            a /= 10;\n            b /= 10;\n            if (found == 4) {\n                break;\n            } \n        }\n\n        if (found <= 1) {\n            return found == 0;\n        }\n        if (found == 2 || found == 3) {\n            Arrays.sort(ad);\n            Arrays.sort(bd);\n            return a == b && Arrays.equals(ad, bd);\n        }\n        // found == 4\n        // need to get a matching pair first with the same indices,\n        // then all digits should match in any order\n        for (int i = 0; i < 3; i++) {\n            for (int j = i+1; j < 4; j++) {\n                if (ad[i] == bd[j] && ad[j] == bd[i]) {\n                    Arrays.sort(ad);\n                    Arrays.sort(bd);\n                    // a == b -> check if the rest digits are equal, found 5+ case\n                    return a == b && Arrays.equals(ad, bd);\n                }\n            }\n        }\n        return false;\n    }\n}\n```\n\n# Code - O(N * D^4)\n\nAnother version based on hints from the task.\nComputing all possible 2-swap variations on the fly and counting previously seen variations of the current number.\nIt\'s passes all test cases in **1.6s** -vs- **5.4s** for the O(N^2)  approach above.\n\n```java []\nclass Solution {\n    static int[] pow10 = {1, 10, 100, 1_000, 10_000, 100_000, 1_000_000};\n    static Set<Integer> variations = new HashSet<>();\n\n    public int countPairs(int[] nums) {\n        // arr[seen_number_variation] = fequency\n        Map<Integer, Integer> frequences = new HashMap<>();\n        int result = 0;\n        for (int value : nums) {\n            result += frequences.getOrDefault(value, 0);\n            // getting all potential 2-diff variations\n            Set<Integer> twoSwapVariations = new HashSet<>();\n            for (int oneSwapVariation : new HashSet<>(allOneSwapVariations(value))) {\n                twoSwapVariations.addAll(allOneSwapVariations(oneSwapVariation));\n            }\n            for (int twoSwapVariation : twoSwapVariations) {\n                frequences.compute(twoSwapVariation, (k,v) -> (v != null ? v : 0) + 1);\n            }\n        }\n        return result;\n    }\n\n    private Set<Integer> allOneSwapVariations(int number) {\n        variations.clear();\n        variations.add(number);\n        int maxDigits = 7;\n        // try swaping any pair of digits\n        for (int i = 0; i < maxDigits; i++) {\n            for (int j = i+1; j < maxDigits; j++) {\n                int di = (number / pow10[i]) % 10;\n                int dj = (number / pow10[j]) % 10;\n                if (di == dj) {\n                    continue;\n                }\n                // swapping digits i and j\n                int diff1variation = number\n                    - di * pow10[i] + di * pow10[j]\n                    - dj * pow10[j] + dj * pow10[i];\n                variations.add(diff1variation);\n            }\n        }\n        return variations;\n    }\n}\n```
['Java']