Skip to main content
Talentd

Count Pairs Of Similar Strings - Solution & Explanation

EasyArrayHash TableStringBit Manipulation11 min readAsked at: Oracle, IBM, Adobe +1
Practice this problem

Problem Statement

You are given a 0-indexed string array words.

Two strings are similar if they consist of the same characters.

  • For example, "abca" and "cba" are similar since both consist of characters 'a', 'b', and 'c'.
  • However, "abacba" and "bcfd" are not similar since they do not consist of the same characters.

Return the number of pairs (i, j) such that 0 <= i < j <= word.length - 1 and the two strings words[i] and words[j] are similar.

 

Example 1:

Input: words = ["aba","aabb","abcd","bac","aabc"]
Output: 2
Explanation: There are 2 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. 
- i = 3 and j = 4 : both words[3] and words[4] only consist of characters 'a', 'b', and 'c'.

Example 2:

Input: words = ["aabb","ab","ba"]
Output: 3
Explanation: There are 3 pairs that satisfy the conditions:
- i = 0 and j = 1 : both words[0] and words[1] only consist of characters 'a' and 'b'. 
- i = 0 and j = 2 : both words[0] and words[2] only consist of characters 'a' and 'b'.
- i = 1 and j = 2 : both words[1] and words[2] only consist of characters 'a' and 'b'.

Example 3:

Input: words = ["nba","cba","dba"]
Output: 0
Explanation: Since there does not exist any pair that satisfies the conditions, we return 0.

 

Constraints:

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 100
  • words[i] consist of only lowercase English letters.

Approach Overview

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.

Approach 1: Set Reduction Approach

This approach involves converting each word into a set of characters. If two words have the same set of characters, they are similar. Convert the string into a set of characters and compare these sets to identify similar words.

We first convert each word in the list into a set of unique characters. We then compare each pair of sets to see if they are equal. If they are, the words are similar, and we increase our count.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(n^2 * m) where n is the number of words and m is the average length of words due to set comparisons.
Space Complexity: O(nm) for storing the sets of characters.

Try this approach in the editor →

Approach 2: Hash Map Character Signature Approach

This approach involves creating a 'signature' for each word using a hashable descriptor such as sorted unique characters. Use a hashmap to count these signatures, and calculate the number of pairs from these counts.

This Java solution uses a HashMap to track the frequency of each sorted character string (signature). Each pair of matching signatures contributes to the count according to combinations formula nC2 = n*(n-1)/2.

Code

JavaC#

Java

C#

Complexity

Time Complexity: O(n * m log m) due to sorting.
Space Complexity: O(n) because of the hashmap to store counts.

Try this approach in the editor →

Approach 3: Hash Table + Bit Manipulation

For each string, we can convert it into a binary number of length 26, where the i-th bit being 1 indicates that the string contains the i-th letter.

If two strings contain the same letters, their binary numbers are the same. Therefore, for each string, we use a hash table to count the occurrences of its binary number. Each time we add the count to the answer, then increment the count of its binary number by 1.

The time complexity is O(L), and the space complexity is O(n). Here, L is the total length of all strings, and n is the number of strings.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Set Reduction Approach

Time Complexity: O(n^2 * m) where n is the number of words and m is the average length of words due to set comparisons.
Space Complexity: O(nm) for storing the sets of characters.

Hash Map Character Signature Approach

Time Complexity: O(n * m log m) due to sorting.
Space Complexity: O(n) because of the hashmap to store counts.

Hash Table + Bit Manipulation—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Set Reduction Pair ComparisonO(n² * k)O(k)Small input sizes or when implementing a quick brute-force check
Hash Map Character Signature (Bitmask)O(n * k)O(n)General case and interview settings where efficient grouping is required

Video Solution

2506. Count Pairs Of Similar Strings | Weekly Contest 324 | LeetCode 2506 • Bro Coders • 2,707 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Pairs Of Similar Strings easy or hard?
Count Pairs Of Similar Strings is classified as an Easy problem on LeetCode with a high acceptance rate around 70%+. The main challenge is recognizing that only the set of characters matters, which allows grouping strings using hashing or bit manipulation.
Count Pairs Of Similar Strings Python/Java solution
Python and Java implementations usually build a signature for each string and store counts in a hash map. Python solutions often use set reduction or bitmasks, while Java implementations commonly use integer bitmasks combined with HashMap frequency counting.
How to solve Count Pairs Of Similar Strings in O(n)?
Treat each string as a set of characters and encode that set into a fixed signature such as a 26-bit mask. Insert the mask into a hash map and track how many times it appears. Each repeated signature adds pairs with previously seen strings, producing an overall O(n * k) algorithm.
What is the best approach for Count Pairs Of Similar Strings?
The most efficient approach uses a hash map with a character signature for each string. Represent the character set using a 26-bit bitmask and store frequencies of each mask. When the same mask appears again, it forms new pairs with previous occurrences. This solution runs in O(n * k) time and O(n) space.
Is Count Pairs Of Similar Strings asked at Google/Amazon/Meta?
Problems involving character signatures, hash maps, and bitmasking frequently appear in interviews at companies like Amazon, Google, and Meta. While the exact problem may vary, the underlying idea of grouping strings by character set is a common pattern.
What data structure is used in Count Pairs Of Similar Strings?
The core data structure is a hash map that groups strings by their canonical character signature. The signature can be represented using a bitmask integer or a sorted/unique character representation. This enables constant-time grouping and pair counting.
What is the time complexity of Count Pairs Of Similar Strings?
The optimal solution runs in O(n * k) time where n is the number of strings and k is the average string length. Each string is scanned once to build its character signature. A hash map lookup then counts matching signatures in constant average time.

Ready to solve this problem?

Practice Count Pairs Of Similar Strings with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count the Number of Consistent Strings

Next

Number of Good Paths