FAST Java sol. (HashMap + bitmasking)
ApproachWe can use bitmasks to represent combinations of present/absent characters in a String, such that any two "similar" strings as defined in the question w
# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can use bitmasks to represent combinations of present/absent characters in a String, such that any two "similar" strings as defined in the question will have identical bitmasks. This will greatly improve time efficiency, as operating on these integers will work much quicker than performing many string operations.\n\nUsing a HashMap is an effective method for tracking the frequencies of each unique bitmask because it allows for constant-time lookup.\n\nFor every word, generate a 26-bit bitmask by:\n. beginning with 0 as the mask,\n. for each character, convert to an index by subtracting from it the numerical representation of the character \'a\'. (c - \'a\')\n. left-shifting the integer value 1 as many times as this index\n. applying the bitwise or-equals operator between the current mask and the variable above\n\nAfter generating the bitmask, increment its corresponding entry in the map (or create an entry with value 1). This can be quickly done using getOrDefault as shown in the code.\n\nNext, for every value in the map greater than 1, add to the total the number of possible combinations of pair of its values using the formula for combinations.\n\n# Complexity\n- Time complexity: O(n)\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n\n- Space complexity: O(mn)\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Code\n```java []\nclass Solution {\n    public int similarPairs(String[] words) {\n        //create bitmask-to-frequency map\n        //for each word, generate a 26-bit bitmask and increment its frequency in the map\n        // next, for every value in the map that appears more than once, calculate the # of combinations\n        // return cumulative total of combinations\n\n\n\n        Map<Integer, Integer> table = new HashMap<Integer, Integer>();\n        int bitmask;\n        for (String w: words) {\n            bitmask = 0;\n            for (char c : w.toCharArray()) {\n                bitmask |= (1 << c - \'a\');\n            }\n            table.put(bitmask, table.getOrDefault(bitmask, 0) + 1);\n        }\n        int total = 0;\n        for (int c : table.values()) {\n            if (c > 1) total += (((c)  *(c - 1)) / (2));\n        }\n        return total;\n\n        \n    }\n\n    \n}\n```
['Hash Table', 'String', 'Bit Manipulation', 'Java']