Permutation Set Intersections, Sliding Window | O(𝑛²+𝑛𝑚⁴), O(𝑛𝑚⁴) | 28.00%, 5.33%
See brute force method used for a simpler variant of this problem in 3265. Count Almost Equal Pairs I where number of swaps is at most once.\n# Intuition\n Desc
*See brute force method used for a simpler variant of this problem in [3265. Count Almost Equal Pairs I](https://leetcode.com/problems/count-almost-equal-pairs-i/solutions/6110920/brute-force-o-o-35-77-96-50/) where number of swaps is at most once.*\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis problem extends the concept of "almost equal" by allowing up to two swaps of digits within either numbers. With two swaps, there may be up to 4 digit mismatches, even 3 mismatches, as a single digit may be swapped twice with different digits. This sheer number of possible combinations means a brute-force comparison method will be inefficient.\n\nOur approach **precomputes all possible \'almost equal\' permutations** of every number, and uses **set intersections** to count the number of previous visited numbers that are almost equal to the current number, while leveraging **digit-padding to handle leading zeros** for consistent string manipulation. This approach combines an <ins>optimized brute force</ins> for precomputing all permutation sets, with a <ins>greedy sliding window</ins> to count pair overlaps with visited numbers.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n- Convert all numbers to 7-digit strings with leading zeros (if necessary).\n- Generate and store in a set "almost equal" variants for each number, considering:\n    - No swaps.\n    - One swap (2 mismatches).\n    - Two swaps.\n        - 2 separate pairs to swap (4 mismatches)\n        - 2 overlapping pairs to swap (3 mismatches)\n- Use a sliding set approach to count valid pairs:\n    - Maintain a counter `left_set` of previously seen numbers.\n    - For each new number, find the intersection of its "almost equal" set with `left_set`.\n    - Increment the count by the sum of occurrences of the intersecting elements in `left_set`.\n- Update `left_set` with the current number.\n# Complexity\n*where $n$ is the number of elements in `nums`, and $m$ is the maximum number of digits per number.*\n- **Time complexity: O(\uD835\uDC5B\xB2+\uD835\uDC5B\uD835\uDC5A\u2074)**\nFor precomputing every possible almost equal variant of all $n$ numbers of maximum $m$ digits, and comparing these variants with all $n$ numbers to find number of overlaps.\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n- **Space complexity: O(\uD835\uDC5B\uD835\uDC5A\u2074)**\nFor storing all possible almost equal variant of every number of maximum $m$ digits in `nums`.\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n| Runtime    | Memory |\n| -------- | ------- |\n| **6776** ms &#124; beats **28.00%** | **119.82** MB &#124; beats **5.33%**|\n```python3 []\nclass Solution:\n    def countPairs(self, nums: list[int]) -> int:\n        def convert_to_len7(s:str) -> str:\n            s = s.zfill(7)\n            return s\n        # given 1 <= nums[i] < 10^7, nums[i] has to be 7 digits or less\n        n = len(nums)\n        output = 0\n        list_of_sets = []\n        for i in range(n):\n            num = str(nums[i])\n            num = convert_to_len7(num)\n            nums[i] = num\n            possible_1,possible_2 = set(),set()\n\n            # No swaps\n            possible_2.add(num)\n            # 1 swap\n            for j in range(6):\n                for k in range(j+1,7):\n                    if num[j] != num[k]:\n                        p = num[:j] + num[k] + num[j+1:k]+ num[j] + num[k+1:]\n                        if p not in possible_1:\n                            possible_1.add(p)\n                            possible_2.add(p)\n            # 2 swaps\n                            for x in range(6):\n                                for y in range(x+1,7):\n                                    if p[x] != p[y]:\n                                        newnum = p[:x]+p[y]+p[x+1:y]+p[x]+p[y+1:]\n                                        possible_2.add(newnum)\n\n            list_of_sets.append(possible_2)\n\n        from collections import Counter\n        left_set = Counter({nums[0]:1})\n        # print(left_set)\n        for i in range(1,n):\n            common_elements = list_of_sets[i].intersection(left_set.keys())\n            output += sum(left_set[element] for element in common_elements)\n            left_set.update({nums[i]:1})\n\n        return output\n```\n# Detailed Approach\n1. Preprocessing:\n    - Convert each number to a 7-digit string using `zfill()`.\n    - Generate all "almost equal" variants for each number to store in set `possible_2`:\n        - No swaps: Add the number itself to the set.\n        - One swap: For every pair of positions (`i`, `j`) in the string:\nSwap digits and add the result to the set.\n        - Two swaps:\n            - For each one-swap variant, for every new pair of positions (`x`, `y`), swap digits again and add the result.\n    - Append set `possible_2` to `lists_of_sets`, which will contain  \'almost equal variants\' for all corresponding numbers in `nums`.\n2. Count Valid Pairs:\n    - Initialize an empty counter `left_set` to store occurrences of previously seen numbers.\n    - For each number\'s set of variants:\n        - Find the intersection of its set with the keys in `left_set` [creates a set `common_elements` of numbers that appear in both `left_set` (as keys), and in `list_of_sets[i]` (ie.`possible_2`)].\n        - For each overlapping variant, add the count (value) from `left_set` to the result `output`.\n    - Update `left_set` by adding 1 count to the base number (`nums[i]` visited.\n3. Return Result:\n    - The final count `output` represents the number of valid pairs.\n\n# Detailed Complexity Breakdown\n*where $n$ is the number of elements in `nums`, and $m$ is the maximum number of digits per number.*\n### Time Complexity: $O(\uD835\uDC5B^2 + nm^4)$\n1. Preprocessing:\n    - $O(n)$ time is taken in the outer loop to process $n$ base numbers in `nums`. For each number:\n        - Padding is performed in $O(m)$ to represent the number as a m-digit string. \n        - Zero Swap variants adds the original number to the set taking $O(1)$ time.\n        - To find One Swap variants, each pair of digits `(i,j)` is compared, taking $O(m^2)$ time.\n        - To find Two Swaps variants, for each one-swap results, the digits are iterated through again to compare each pair of digits `(x,y)`, taking $O(m^2)$ time.\n    - Therefore the time taken to preprocess and generate "almost equal" variants for all numbers is $O(n(m+1+m^4)) = O(nm^4)$.\n2. Pair Counting:\n    - $n$ elements are processed to find the count of intersections between its variants and previously visited numbers, the outer loop takes $O(n)$ time.\n    - In the inner loop:\n        - From the preprocessing step, each set of variants has a maximum size of $O(m^4)$.\n        - `left_set` contains up to $n$ elements.\n        - Set intersection takes $O(\\min(len(set1), len(set2))) = O(\\min(m^4, n))$ time. For simplicity (overestimate), we treat this as $O(n + m^4)$.\n    - Therefore, the time taken for the pair counting step is $O(n(n+m^4)) = O(n^2 + nm^4)$\n3. Overall Time Complexity:\n    - Combining preprocessing and counting, time complexity is $O(nm^4 + n^2 + nm^4) = O(n^2+nm^4)$\n\n### Space Complexity: $O(nm^4)$\n1. Storage for Variant Sets:\n    - Each number generates a set with up to $m^4$ elements, hence needing $O(nm^4)$ space for $n$ numbers.\n2. Counter dictionary `left_set`:\n    - Tracks the counts of up to $$n$$ base numbers, taking $O(n)$ space.\n3. Intersection set `common_elements`:\n    - Contains up to $\\min(m^4, n)$ intersecting elements between the variant set and `left_set`.\n\n# Best, Worst, and Average Case Analysis\n### Time Complexity\n1. Best-case: $O(n^2)$\n    - When every number has no almost equal variant other than itself (eg. the number \'7777777\'), so all $O(m^4)$ operations are reduced to $O(1)$.\n2. Worst-case: $O(n^2+nm^4)$\n    - Every number has no repeating digits (eg. \'1234567\'), meaning there are the full $m^4$ almost equal variants.\n3. Average-case: $O(n^2+nm^4)$\n    - On average, the every number may contain a mix of repeating and non-repeating digits (eg. \'1122345\'), thus having less than but still significantly close to $m^4$ almost equal variants.\n\n### Space Complexity\nIn all cases, $O(n)$ space is still required for `left_set`.\n1. Best-case: $O(2n)$ = $O(n)$\n    - When every number has no almost equal variant other than itself (eg. the number \'7777777\'), so all $O(m^4)$ operations are reduced to $O(1)$, and there will be $n$ almost equal variants (equal \'variants\' of $n$ numbers).\n2. Worst-case: $O(n+nm^4+\\min(n,m^4))$ =  $O(nm^4)$\n    - Every number has no repeating digits (eg. \'1234567\'), meaning there are the full $m^4$ almost equal variants.\n3. Average-case: $O(n+nm^4+\\min(n,m^4))$ =  $O(nm^4)$\n    - On average, the every number may contain a mix of repeating and non-repeating digits (eg. \'1122345\'), thus having less than but still significantly close to $m^4$ almost equal variants.\n### Summary\n| Scenario | Time Complexity | Space Complexity |\n| - | - | - |\n| Best Case | $O(n^2)$ | $O(n)$ |\t\n| Worst Case | $O(n^2+nm^4)$ | $O(nm^4)$ |\n| Average Case | $O(n^2+nm^4)$ | $O(nm^4)$ |\n***\nCheck out my solutions to other problems here! \uD83D\uDE03\n*https://leetcode.com/discuss/general-discussion/5942132/my-collection-of-solutions*\n***
['Sliding Window', 'Combinatorics', 'Counting', 'Python3']