LeetCode 1002: Find Common Characters

Problem Restatement

We are given an array of strings words.

We need to return a list of all characters that appear in every string in words, including duplicates.

If a character appears k times in every string, we include it k times in the answer.

The answer can be returned in any order.

The official constraints state that 1 <= words.length <= 100, 1 <= words[i].length <= 100, and each words[i] contains only lowercase English letters.

Input and Output

Function shape:

def commonChars(words: list[str]) -> list[str]:
    ...

Examples

Example 1:

words = ["bella", "label", "roller"]

Character frequencies:

Common characters:

["e", "l", "l"]

Example 2:

words = ["cool", "lock", "cook"]

Character frequencies:

Common characters:

["c", "o"]

Key Insight

A character is common to all words if and only if its minimum frequency across all words is at least 1.

The number of times we include a character is its minimum frequency across all words.

So we compute the element-wise minimum of the frequency arrays for all words.

Algorithm

1. Start with the frequency array of the first word.
2. For each subsequent word, take the element-wise minimum with the current minimum array.
3. Expand the final minimum array into a character list.

Correctness

A character c appears at least min_freq[c] times in every word because min_freq[c] is the minimum frequency of c across all words.

We include c exactly min_freq[c] times. This is the maximum number of copies of c we can include while guaranteeing each copy appears in every word.

Edge Cases

• Duplicates usually matter; store counts when a set would lose necessary multiplicity.
• Update the frequency structure in the same order the invariant assumes.
• Check empty or one-element inputs if the problem allows them.

Complexity

Let n = len(words) and m be the average word length.

Common Pitfalls

• Do not optimize away the invariant; the code should still make it clear what condition is being maintained.
• Prefer problem-specific names over one-letter variables once the logic becomes stateful.

Implementation

from collections import Counter

class Solution:
    def commonChars(self, words: list[str]) -> list[str]:
        min_freq = Counter(words[0])

        for word in words[1:]:
            word_freq = Counter(word)
            for ch in min_freq:
                min_freq[ch] = min(min_freq[ch], word_freq.get(ch, 0))

        result = []
        for ch, count in min_freq.items():
            result.extend([ch] * count)

        return result

Code Explanation

Initialize the minimum frequency from the first word:

min_freq = Counter(words[0])

For each following word, reduce counts to the minimum:

for ch in min_freq:
    min_freq[ch] = min(min_freq[ch], word_freq.get(ch, 0))

If a character from words[0] does not appear in a later word, its count drops to 0.

Expand the final counts into a list:

result.extend([ch] * count)

Testing

def run_tests():
    s = Solution()

    assert sorted(s.commonChars(["bella", "label", "roller"])) == sorted(["e", "l", "l"])
    assert sorted(s.commonChars(["cool", "lock", "cook"])) == sorted(["c", "o"])
    assert sorted(s.commonChars(["abc", "abc"])) == sorted(["a", "b", "c"])
    assert s.commonChars(["a", "b"]) == []

    print("all tests passed")

run_tests()