Use `collections.Counter`

There is no MultiSet (a set that allows the same elements) by default in Python, but you can use collections.Counter instead. It is not just a MultiSet but has a convenient method for counting, so it can be used in various situations.

Reference: https://docs.python.org/ja/3/library/collections.html#collections.Counter

Let's take LeetCode as an example.

169. Majority Element

Find the mode of nums.

You can use most_common as below.

class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return collections.Counter(nums).most_common(1)[0][0]

242. Valid Anagram

Asks if the two strings s and t are anagrams.

Being an anagram means that it appears the same number of times. Therefore, just compare collections.Counter with==.

class Solution:
    def isAnagram(self, s: str, t: str) -> bool:
        return collections.Counter(s) == collections.Counter(t)

299. Bulls and Cows

Find the number of matches in the "position and number" and the number of matches in the number guessing game.

"Position and number" can be extracted by zip and compared. For the number that matches only the number, find the intersection with "&" and count the number (values).

class Solution:
    def getHint(self, secret: str, guess: str) -> str:
        co = collections.Counter
        a = sum(i == j for i, j in zip(secret, guess))
        b = sum((co(secret) & co(guess)).values()) - a
        return f"{a}A{b}B"

347. Top K Frequent Elements

Find the top K high frequency elements.

As it is, use most_common.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        return [i for i, _ in collections.Counter(nums).most_common(k)]

350. Intersection of Two Arrays II

Find the intersection of the two lists in the list.

Elements can be obtained with ʻelements`.

class Solution:
    def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        c = collections.Counter(nums1) & collections.Counter(nums2)
        return list(c.elements())

383. Ransom Note

Asks if each character in ransomNote is included in the magazine. Each character in magazine can be used only once.

You can calculate the difference set with " - ".

class Solution:
    def canConstruct(self, ransomNote: str, magazine: str) -> bool:
        return not (collections.Counter(ransomNote) - collections.Counter(magazine))

387. First Unique Character in a String

Find the index of the first unique character.

It only returns the one with 1 appearance.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        for k, v in collections.Counter(s).items():
            if v == 1:
                return s.index(k)
        return -1

By the way, "136. Single Number", which finds the number that only one exists, should be accumulated by XOR.

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in nums:
            res ^= i
        return res

389. Find the Difference

Add one character to the string s and let the shuffled string be t. Ask for the added character.

It can be calculated with the difference set.

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        return list((collections.Counter(t) - collections.Counter(s)).keys())[0]

532. K-diff Pairs in an Array

Find the number of element pairs for which the difference is k.

collections.Counter can use ʻitems ()` just like a dictionary. The elements are the value and the number.

class Solution:
    def findPairs(self, nums: List[int], k: int) -> int:
        c = collections.Counter(nums)
        return sum(k > 0 and n + k in c or k == 0 and f > 1 for n, f in c.items())

657. Robot Return to Origin

Find out if the end point of the robot after movement is the origin.

collections.Counter can useget (key)like a dictionary. It returns to the origin when the number of left movements and the number of right movements are equal, and the number of downward movements and the number of up movements are equal. You can use str.count, but collections.Counter is better.

class Solution:
    def judgeCircle(self, moves: str) -> bool:
        c = collections.Counter(moves)
        return c.get("L", 0) == c.get("R", 0) and c.get("D", 0) == c.get("U", 0)

819. Most Common Word

Find the mode word that is not included in banned (uppercase letters are considered lowercase).

You can use most_common because it is the most frequent word.

class Solution:
    def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
        c = collections.Counter(re.findall(r"\w+", paragraph.lower()))
        return next(s for s, _ in c.most_common() if s not in banned)

893. Groups of Special-Equivalent Strings

If even-numbered or odd-numbered numbers are exchanged and match, they are considered to be in the same group. Find the number of groups.

Use collections.Counter by changing the odd numbers to uppercase. You can also find the group by doing set (tuple (sorted (c.items ()))).

class Solution:
    def numSpecialEquivGroups(self, A: List[str]) -> int:
        cc = [collections.Counter(i[::2].upper() + i[1::2]) for i in A]
        return len(set(tuple(sorted(c.items())) for c in cc))

Digression

I don't use more_itertools to match LeetCode, but it makes it simpler.

Reference: Example of LeetCode answer using collections.Counter

[PYTHON] Use collections.Counter

Use collections.Counter

Digression

Use `collections.Counter`