💬 Discord
Sign In
NeetCode #84LC-1002EasyArrays & Hashing
← Back to All Problems

#84 · #1002 · Find Common Characters(查找共用字符)

📌 Problem Statement & Constraints

Given an array of strings words, return an array of all characters that appear in all strings, including duplicates (a character appearing twice in every word is listed twice). Constraints: 1 <= words.length <= 100, 1 <= words[i].length <= 100, lowercase letters.

💡 Core Algorithmic Approaches

  1. Count the characters in each word.
  2. For each character, the number of times it can appear in the answer is the minimum of its counts across all words.
  3. Iterate the distinct characters of the first word, compute the minimum count, and append that many copies.
  4. Iterating only the first word's characters avoids redundant work, since a character absent from the first word cannot be common.

💻 Benchmark Python3 Implementation

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        from collections import Counter
        cnts = [Counter(w) for w in words]
        res = []
        for ch in set(words[0]):           # only characters of the first word can qualify
            m = min(c[ch] for c in cnts)   # 0 if absent from any word
            res.extend([ch] * m)
        return res

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(total characters): counting each word once plus a constant-size scan over the alphabet.
💾 Space Complexity
O(k) for the counters, k <= 26.

⚠️ Interview Pitfalls & Follow-ups

  • Using a set intersection: this loses multiplicity, so a character appearing twice in every word would be listed only once.
  • Iterating the whole alphabet instead of the first word: correct but does unnecessary work; iterating set(words[0]) is tighter.
  • Taking the sum or maximum of the counts: the correct aggregation is the minimum.
  • Returning characters instead of strings: the return type is a list of single-character strings, which extend([ch] * m) produces correctly.