LC-2506 Easy LeetCode

2506. Count Pairs Of Similar Strings

Array Hash Table String Bit Manipulation Counting

Read the full problem statement on LeetCode.

Difficulty: easy Acceptance: 72% Topics: Array, Hash Table, String, Bit Manipulation, Counting

Reading material

Arrays & Hashing 12 min Strings 12 min Bit Manipulation 10 min

Reference solution (spoiler · python)

# Time:  O(n * l)
# Space: O(n)

import collections
import itertools


# freq table, bitmask
class Solution(object):
    def similarPairs(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        cnt = collections.Counter()
        result = 0
        for w in words:
            mask = reduce(lambda total, x: total|x, itertools.imap(lambda c: 1<<(ord(c)-ord('a')), w))
            result += cnt[mask]
            cnt[mask] += 1
        return result

Solution from kamyu104/LeetCode-Solutions · MIT