Find Common Characters — Frequency Intersection Across String Arrays

Problem Statement#

Given a string array words, return an array of all characters that show up in all strings within the words array (including duplicates). You may return the answer in any order.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters.

Example 1:
Input:  words = ["bella", "label", "roller"]
Output: ["e", "l", "l"]
Explanation: 'e' appears in all three strings (min freq = 1).
             'l' appears at least twice in all three strings (min freq = 2).

Example 2:
Input:  words = ["cool", "lock", "cook"]
Output: ["c", "o"]
Explanation: 'c' and 'o' each appear in all three strings with min freq 1.

Example 3:
Input:  words = ["ab", "cd"]
Output: []
Explanation: No character appears in both strings.

Why This Problem Matters#

Find Common Characters introduces the frequency intersection pattern — computing the element-wise minimum across multiple frequency maps. This is more nuanced than a simple set intersection, because a character appearing twice in all strings contributes two copies to the result, while a character appearing once in one string and five times in another contributes only once (the minimum).

This pattern has direct real-world analogues: finding the minimum available inventory across multiple warehouses, computing the common skill set across a team (minimum proficiency level for each skill), or identifying features available on all devices in a heterogeneous fleet. Google, where this problem is a frequent screen, values candidates who can abstract beyond the specific "characters in strings" framing to the general "multiset intersection" pattern.

The problem also tests your ability to choose the right data structure for the job. A simple set (without counts) incorrectly handles the duplicate character case — it would return one copy of 'l' from ["bella", "label", "roller"] instead of two. You need a multiset, represented here as a fixed-size frequency array.

From an algorithm design perspective, the approach teaches "accumulate then answer" thinking: instead of trying to identify common characters while iterating, build the full frequency structure for each word and then combine them. This separation of concerns makes the code cleaner and the algorithm easier to reason about.

The Core Insight#

The result for each character is determined by its minimum frequency across all words. If 'l' appears 3 times in word A, 2 times in word B, and 4 times in word C, then 'l' contributes min(3, 2, 4) = 2 copies to the result.

The algorithm:

1. Initialize a min_freq array of size 26, all set to infinity (or to the frequency of the first word).
2. For each subsequent word, compute its frequency array and take the element-wise minimum with min_freq.
3. After processing all words, expand min_freq back into a list of characters (each character repeated by its min frequency).

The element-wise minimum is the key operation. It corresponds to the multiset intersection: A ∩ B where count(x in A ∩ B) = min(count(x in A), count(x in B)).

Python's Counter class supports this directly with the & operator: Counter(a) & Counter(b) returns the intersection (element-wise minimum). Chaining this across all words gives the final answer. However, the manual array approach is more transparent and more efficient in practice (no Counter allocation overhead per word).

Visual Dry Run#

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

Step 1 — Frequency of "bella":

min_freq = {a:1, b:1, e:1, l:2}

Step 2 — Frequency of "label", then take element-wise min:

"label": {a:1, b:1, e:1, l:2}

Element-wise min: {a:1, b:1, e:1, l:2} (no change, same frequencies)

Step 3 — Frequency of "roller", then take element-wise min:

"roller": {e:1, l:2, o:1, r:2}

Element-wise min with previous: {a:0, b:0, e:1, l:2} — 'a' and 'b' drop to 0.

Result expansion: 'e' (1 copy), 'l' (2 copies) → ["e", "l", "l"]

Solution (Optimal)#

from collections import Counter
 
def commonChars(words: list[str]) -> list[str]:
    # Start with the frequency of the first word
    min_freq = Counter(words[0])
 
    # Intersect (element-wise min) with each subsequent word
    for word in words[1:]:
        min_freq &= Counter(word)
 
    # Expand the frequency map back into a list of characters
    return list(min_freq.elements())
 
 
# Manual array approach — more explicit and slightly faster
def commonChars_array(words: list[str]) -> list[str]:
    # Initialize with large values (will be overwritten)
    min_freq = [float('inf')] * 26
 
    for word in words:
        freq = [0] * 26
        for ch in word:
            freq[ord(ch) - ord('a')] += 1
        # Take element-wise minimum
        for i in range(26):
            min_freq[i] = min(min_freq[i], freq[i])
 
    # Expand to character list
    result = []
    for i in range(26):
        result.extend([chr(ord('a') + i)] * min_freq[i])
    return result

var commonChars = function(words) {
    // Initialize min_freq from the first word
    const minFreq = new Array(26).fill(0);
    for (const ch of words[0]) {
        minFreq[ch.charCodeAt(0) - 97]++;
    }
 
    // For each subsequent word, take element-wise minimum
    for (let w = 1; w < words.length; w++) {
        const freq = new Array(26).fill(0);
        for (const ch of words[w]) {
            freq[ch.charCodeAt(0) - 97]++;
        }
        for (let i = 0; i < 26; i++) {
            minFreq[i] = Math.min(minFreq[i], freq[i]);
        }
    }
 
    // Expand to character array
    const result = [];
    for (let i = 0; i < 26; i++) {
        for (let j = 0; j < minFreq[i]; j++) {
            result.push(String.fromCharCode(97 + i));
        }
    }
    return result;
};

Complexity Analysis

Both approaches are O(n * m) time and O(1) space (26-element arrays for the fixed ASCII lowercase alphabet). The Counter approach is more Pythonic; the array approach is more explicit and avoids Counter object allocation overhead.

Common Mistakes#

• Using a set intersection instead of a multiset intersection. set("bella") & set("label") & set("roller") gives {'e', 'l'} — only one 'l' instead of two. The problem requires counting duplicates, which demands frequency arrays or Counters, not sets.
• Forgetting to initialize min_freq correctly. If you initialize min_freq to all zeros, the element-wise minimum with any word will always be zero, and you will return an empty list. Initialize from the first word (or with infinity).
• Building a global frequency map instead of per-word frequencies. Some candidates count characters across all words combined, then try to filter. This does not correctly compute per-word minimums.
• Off-by-one in character encoding. ord('a') is 97. Subtracting 97 (or ord('a')) gives the 0-indexed position. Forgetting the subtraction maps 'a' to index 97, which is out of bounds for a 26-element array.
• Not handling the case where min_freq[i] can be float('inf'). This happens if you initialize with infinity and words is empty. Always handle the empty-words edge case separately or initialize from the first word.

Follow-up Questions#

What if words can contain uppercase letters or Unicode characters? Replace the 26-element array with a hash map (Python Counter or JavaScript Map). The algorithm is identical — the min operation becomes min(map1.get(ch, 0), map2.get(ch, 0)).

How would you find characters that appear in at least half the words (not all)? Instead of the element-wise minimum, count how many words each character appears in. For minimum frequency across half-the-words, track the K-th smallest frequency across the word list for each character (partial intersection problem).

What if words arrive as a stream? Maintain a running min_freq array. For each new word, compute its frequency and update min_freq with element-wise minimum. This is O(m) per new word, where m is the word length.

Can you solve this without extra space (O(1) space)? For the lowercase ASCII constraint, the 26-element array counts as O(1) — it is a constant-size allocation. No additional space beyond this is needed.

How does the multiset intersection relate to the set intersection? Set intersection gives characters present in all strings (ignoring frequency). Multiset intersection additionally preserves the minimum occurrence count. Multiset intersection is strictly more informative — it subsumes set intersection.

Key Takeaways#

• LC 1002 Find Common Characters is solved via multiset intersection — element-wise minimum across per-word frequency maps.
• A plain set intersection is wrong because it loses duplicate counts; you need a frequency array or Counter.
• Initialize min_freq from the first word (or with infinity) so the first element-wise minimum is meaningful.
• Time complexity is O(n * m) for n words of average length m; space is O(1) when alphabet is fixed (26 lowercase letters).
• Python's Counter & Counter operator is the idiomatic multiset intersection; chain it across all words.
• Expand the final frequency map back to a list with Counter.elements() or repeated character pushes.
• This pattern generalizes to multi-warehouse minimum stock, common skill sets across teams, and feature intersections across heterogeneous devices.

Related Problems#

• LC 1002 — Find Common Characters: This problem.
• LC 242 — Valid Anagram: Uses frequency arrays for character counting — the same building block.
• LC 383 — Ransom Note: One-directional frequency coverage check.
• LC 349 — Intersection of Two Arrays: Set intersection (not multiset) — simpler version of this problem.
• LC 350 — Intersection of Two Arrays II: Multiset intersection for arrays — same concept applied to integers instead of string characters.
• LC 438 — Find All Anagrams in a String: Frequency matching between a window and a pattern — combines frequency arrays with sliding window.