Abstract / Summary

Count how many pairs of strings are similar by having the same pattern of character occurrences.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 74% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Bit Manipulation
• Counting
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method similarPairs that receives a list of lowercase alphabetic strings and returns the number of unordered pairs of strings that share exactly the same set of distinct characters. The algorithm relies on a compact bitmask representation for each word and a frequency map to count how many times each distinct character set has been observed while iterating through the input.

Key Steps

Fingerprint Generation

A nested helper function fingerprint converts a word into a 26-bit integer where each bit corresponds to a letter of the English alphabet. The function starts with a zero mask, iterates over the characters of the word, and sets the appropriate bit using a left shift based on the character’s offset from 'a'. The resulting integer uniquely identifies the set of distinct letters present in the word, irrespective of order or multiplicity.

def fingerprint(w):
    bitmask = 0
    for c in w:
        bitmask |= 1 << (ord(c) - ord("a"))
    return bitmask

Counting Pairs

The main loop traverses the input list words. For each word, it computes the fingerprint f. A dictionary have (implemented as defaultdict(int)) stores how many times each fingerprint has been seen so far. The current contribution to the answer is the count already stored for the same fingerprint, because each previous occurrence forms a new pair with the current word. After adding this contribution to result, the frequency for the fingerprint is incremented.

result = 0
have = defaultdict(int)
for w in words:
    f = fingerprint(w)
    result += have[f]
    have[f] += 1
return result

Edge Cases Handled

When the input list is empty, the loop body never executes, leaving result at its initial value of zero, which correctly reflects that no pairs exist. If the list contains a single word, the same logic applies: the dictionary contains no prior entry for its fingerprint, so the contribution added to result is zero, and the final answer remains zero. Duplicate words are naturally handled because they generate identical fingerprints; each new duplicate adds a number of pairs equal to the count of earlier duplicates, producing the combinatorial count of pairs among identical fingerprints. Words that consist of a single repeated character still produce a correct fingerprint because the bitmask sets only the bit for that character, ignoring repetitions. Words that contain all 26 letters generate a fingerprint with all bits set, and the algorithm treats this case identically to any other fingerprint.

Performance Optimizations

The use of a 26-bit integer to encode the character set is a space-efficient representation that fits comfortably within a standard machine word, allowing constant-time bitwise operations for setting bits. The left-shift and bitwise-or operations inside fingerprint are extremely fast, avoiding the overhead of constructing auxiliary data structures such as sets or arrays for each word. The frequency map have leverages defaultdict(int), which provides O(1) average-time insertion and lookup without the need for explicit existence checks. By updating the answer incrementally as the list is scanned, the algorithm avoids a second pass or nested loops, achieving a single linear traversal over the input. This design ensures that the total work scales directly with the number of words and the length of each word, while keeping auxiliary memory usage proportional to the number of distinct fingerprints encountered.

Imagine a big box of colorful blocks where each block has a letter on it. The code looks at a group of words and decides which ones are similar by seeing which letters they use.

First, there is a way to turn each word into a secret code. Think of this like giving each letter a special number. For every word, the code checks if it has an ‘a’, a ‘b’, and so on. It keeps track of these markings in a small space, creating a unique pattern for every word based only on the letters inside. It does not matter if a word uses a letter once or ten times, because the code only cares that the letter is present.

Next, it walks through all the words one by one. It looks at the secret code for the current word and asks if any words seen before had the exact same code. If other words had the same pattern of letters, it counts them up as pairs. Finally, it remembers the current word by adding its secret code to a list of words already visited, so that the next words can be checked against it too. This helps find all the friends in the list that use the same set of letters.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	Python	Java			C++			TS
	WalkCCC	Python	Java			C++
	leetcode.ca	Python	Java			C++	Go	Rust	TS
	Progiez	Python	Java			C++
github	chandansgowda	Python
	charles-wangkai		Java
	fartem			Ruby
	fsq					C++
	JoshCrozier				JS
	lkwq007	Python
	varunu28		Java
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, Rust, TypeScript
Progiez	C++, Java, Python
chandansgowda	Python
charles-wangkai	Java
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
varunu28	Java

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality