Count Almost Equal Pairs II

A more efficient approach avoids the quadratic complexity by first grouping numbers that are permutations of each other. Since only numbers within the same permutation group can be almost equal, we can process each group independently. Within a group, for each number, we generate all its 'almost equal' variants and use a hash map to quickly count how many previously seen numbers match these variants. This reduces the overall complexity from quadratic to linear.

• First, preprocess the input array. Convert each number to a string of fixed length (e.g., 7) by padding with leading zeros. Then, create a canonical key for each number by sorting its digits. Use a hash map groups to group all numbers that have the same key (i.e., are permutations of each other).
• Initialize total_pairs = 0.
• Iterate through each list of numbers (group) in the groups map.
• For each group, create a new hash map processed_counts to store the frequency of numbers encountered so far within that group.
• Iterate through each number s in the current group:
  • Generate a set S(s) containing all unique strings that can be formed from s by performing 0, 1, or 2 swaps.
    • 0 swaps: s itself.
    • 1 swap: All permutations that are single transpositions.
    • 2 swaps: All permutations that are 3-cycles or compositions of two disjoint 2-cycles.
  • For each variant in the generated set S(s):
    • Add the count of processed_counts.getOrDefault(variant, 0) to total_pairs. This finds pairs with already processed numbers.
  • After checking all variants for s, increment its count in processed_counts: processed_counts.put(s, processed_counts.getOrDefault(s, 0) + 1).
• Return total_pairs.

This method is based on the observation that two numbers can only be almost equal if they are permutations of each other. We can leverage this to optimize the search.

1. Grouping: We first iterate through the nums array. For each number, we create a canonical representation by sorting its digits (after padding it to a fixed length string). We use a HashMap<String, List<String>> to group all numbers that share the same canonical form.

2. Counting within Groups: We then iterate through each group of numbers. For a given group, we know all numbers are permutations of one another. We can count the almost equal pairs within this group efficiently. We use another HashMap<String, Integer> called processed_counts to keep track of the numbers we've seen so far in the group and their frequencies.

3. Variant Generation and Hashing: For each number s in the group, we generate all possible strings that can be obtained by applying at most two swaps. This set of variants, S(s), represents all numbers that are almost equal to s. For every variant in S(s), we check if it exists in processed_counts. If it does, it means we've already processed a number that is almost equal to our current number s. We add its frequency from processed_counts to our total pair count. After processing all variants of s, we update the frequency of s itself in processed_counts.

This process ensures that each valid pair (i, j) with i < j is counted exactly once. The time complexity is dominated by iterating through the numbers and generating their variants, which is much faster than comparing all pairs.

import java.util.*;

class Solution {
    public int countAlmostEqualPairs(int[] nums) {
        Map<String, List<String>> groups = new HashMap<>();
        int maxLen = 0;
        for (int num : nums) {
            maxLen = Math.max(maxLen, String.valueOf(num).length());
        }

        for (int num : nums) {
            String s = String.valueOf(num);
            s = String.format("%" + maxLen + "s", s).replace(' ', '0');
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }

        long totalPairs = 0;
        for (List<String> group : groups.values()) {
            Map<String, Integer> processedCounts = new HashMap<>();
            for (String s : group) {
                Set<String> variants = generateVariants(s);
                for (String variant : variants) {
                    totalPairs += processedCounts.getOrDefault(variant, 0);
                }
                processedCounts.put(s, processedCounts.getOrDefault(s, 0) + 1);
            }
        }
        return (int) totalPairs;
    }

    private Set<String> generateVariants(String s) {
        Set<String> variants = new HashSet<>();
        char[] arr = s.toCharArray();
        int n = arr.length;

        // 0 swaps
        variants.add(s);

        // 1 swap (transpositions)
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                swap(arr, i, j);
                variants.add(new String(arr));
                swap(arr, i, j); // backtrack
            }
        }

        // 2 swaps (3-cycles and two 2-cycles)
        // This can be done by applying a second swap to all 1-swap variants.
        Set<String> oneSwapVariants = new HashSet<>(variants);
        for(String oneSwapStr : oneSwapVariants){
            if(oneSwapStr.equals(s)) continue;
            char[] tempArr = oneSwapStr.toCharArray();
            for (int i = 0; i < n; i++) {
                for (int j = i + 1; j < n; j++) {
                    swap(tempArr, i, j);
                    variants.add(new String(tempArr));
                    swap(tempArr, i, j); // backtrack
                }
            }
        }
        return variants;
    }

    private void swap(char[] arr, int i, int j) {
        char temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}