Find Common Characters Solution in Python

Quick Links

Problem Description

So, you think you can find common characters among a bunch of words? Well, welcome to the “Find Common Characters” problem on LeetCode, where you get to play detective with strings! Imagine you’re at a party, and you want to find out which snacks are common among your friends. You ask each friend what snacks they brought, and you want to know which snacks are a hit across the board. Spoiler alert: it’s not going to be the kale chips!

In this problem, you are given an array of strings, and your task is to find the characters that appear in every single string. If a character appears multiple times in one string, it should be included in the result as many times as it appears in the string with the least occurrences.

Code Solution


import collections
import functools

class Solution:
    def commonChars(self, words: list[str]) -> list[str]:
        return functools.reduce(lambda a, b: a & b,
                                map(collections.Counter, words)).elements()

Approach

The approach used in the code is quite elegant. It leverages Python’s collections.Counter to count the occurrences of each character in the strings. Then, it uses functools.reduce to find the intersection of these counts across all strings. The result is a collection of characters that are common to all input strings, with the correct frequency based on the string with the least occurrences.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O(N * M), where N is the number of strings and M is the average length of the strings.
Space Complexity	O(1) if we consider the character set to be constant (like lowercase English letters), otherwise O(M) for storing the counts.

Real-World Example

Imagine you and your friends are planning a movie night. Each of you has a list of snacks you can bring. You want to find out which snacks everyone can agree on. After some back-and-forth, you realize that popcorn is the only snack that everyone can bring. Just like that, the “Find Common Characters” problem helps you find the common characters across all strings, ensuring that you only get the snacks (or characters) that everyone can agree on!