Count Pairs Of Similar Strings - Video Solutions

Problem Overview: You receive an array of strings. Two strings are considered similar if they contain exactly the same set of characters, regardless of order or frequency. The task is to count how many pairs (i, j) exist such that both strings share the identical character set.

Approach 1: Set Reduction Approach (O(n² * k) time, O(k) space)

Reduce each string to a set of unique characters, then compare every pair of strings. Two strings are similar if their character sets are equal. Iterate through all pairs using nested loops and perform a set comparison for each pair. If the sets match, increment the pair count. This approach is straightforward and easy to implement using string processing and basic array traversal.

The downside is the quadratic pair comparison. For n strings and average length k, building the sets costs O(k) and comparing pairs pushes the total runtime to O(n² * k). Space usage remains O(k) per temporary set. This works fine for small inputs but becomes inefficient when the number of strings grows.

Approach 2: Hash Map Character Signature (O(n * k) time, O(n) space)

A more scalable solution converts each string into a canonical character signature and groups identical signatures using a hash map. The most efficient signature uses a 26‑bit integer mask where each bit represents whether a letter appears in the string. Iterate through the characters and set the corresponding bit using bitwise OR. Strings with the same character set produce identical masks.

Store frequencies of these masks in a hash table. Each time a mask appears again, it forms pairs with all previous strings that had the same mask. If a signature appears f times, it contributes f * (f - 1) / 2 pairs. Building each mask takes O(k), and processing all strings costs O(n * k) time with O(n) additional storage. The bitmask technique leverages bit manipulation to create a compact and fast signature.

Recommended for interviews: Interviewers typically expect the hash map signature approach. The brute-force pair comparison demonstrates understanding of the similarity definition, but the optimized solution shows you can reduce repeated comparisons by hashing canonical representations. Recognizing that only the character set matters, not frequency or order, leads directly to the bitmask optimization.