Problem Description

You are given an array of strings called words. Your task is to find all characters that appear in every single string within this array. If a character appears multiple times in all strings, you need to include it that many times in your result.

For example, if the character 'l' appears at least twice in every string, then 'l' should appear twice in your output. The key point is that you're looking for the common characters across all strings, considering their minimum frequency.

The solution uses a counting approach where it:

1. First counts the frequency of each character in the first word using Counter(words[0])
2. Then for each subsequent word, it counts that word's character frequencies
3. For each character in the running count, it updates the count to be the minimum between the current count and the new word's count - this ensures we only keep characters that appear in all words with their minimum frequency
4. Finally, it uses cnt.elements() to expand the counter back into a list of characters, where each character appears according to its count

The time complexity is O(n * m) where n is the number of words and m is the average length of each word, since we need to process each character in each word.

Intuition

When we need to find common elements across multiple sets, the key insight is to think about intersection. For characters that appear in all strings, we need to track not just their presence but also their frequency.

Consider this: if the letter 'a' appears 3 times in the first string, 2 times in the second string, and 5 times in the third string, then 'a' can only be common to all strings at most 2 times (the minimum frequency). This is because we can't claim 'a' appears 3 times in all strings when the second string only has 2 'a's.

This leads us to the core idea: for each character, we need to find its minimum frequency across all strings. If a character doesn't appear in even one string, its minimum frequency becomes 0, effectively removing it from our result.

We can start by counting characters in the first string as our initial reference. Then, as we examine each subsequent string, we update our counts by taking the minimum between what we currently have and what the new string offers. This process is like repeatedly finding the intersection of character frequencies - we keep narrowing down to only what's truly common.

The beauty of this approach is that by using the minimum operation, we automatically handle both cases: characters that don't appear in all strings (their count becomes 0) and characters that appear with different frequencies (we keep the smallest count that works for all strings).

Solution Approach

The solution uses a counting approach with Python's Counter data structure to efficiently track character frequencies.

Step 1: Initialize the counter

cnt = Counter(words[0])

We start by creating a Counter object from the first word. This gives us a dictionary-like structure where keys are characters and values are their frequencies in the first word. For example, if words[0] = "bella", then cnt = {'b': 1, 'e': 1, 'l': 2, 'a': 1}.

Step 2: Process remaining words

for w in words:
    t = Counter(w)
    for c in cnt:
        cnt[c] = min(cnt[c], t[c])

For each subsequent word in the array:

• Create a temporary counter t for the current word
• For each character c that exists in our running counter cnt, update its count to be the minimum between the current count and the count in word w
• Note that t[c] returns 0 if character c doesn't exist in the current word, which effectively sets cnt[c] to 0

This process ensures that:

• Characters not present in all words will have their count reduced to 0
• Characters present in all words will retain the minimum frequency across all words

Step 3: Generate the result

return list(cnt.elements())

The elements() method of Counter returns an iterator that repeats each character according to its count. Converting this to a list gives us our final answer where each common character appears the correct number of times.

For example, if cnt = {'l': 2, 'e': 1} after processing all words, then list(cnt.elements()) returns ['l', 'l', 'e'].

The time complexity is O(n * m) where n is the number of words and m is the average length of each word. The space complexity is O(1) since we only track at most 26 lowercase English letters.

Example Walkthrough

Let's walk through the solution with a concrete example:

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

Step 1: Initialize with first word

• Start with words[0] = "bella"
• Create counter: cnt = {'b': 1, 'e': 1, 'l': 2, 'a': 1}

Step 2: Process "label"

• Create counter for "label": t = {'l': 2, 'a': 1, 'b': 1, 'e': 1}
• Update cnt by taking minimum frequencies:
  • 'b': min(1, 1) = 1
  • 'e': min(1, 1) = 1
  • 'l': min(2, 2) = 2
  • 'a': min(1, 1) = 1
• After processing: cnt = {'b': 1, 'e': 1, 'l': 2, 'a': 1}

Step 3: Process "roller"

• Create counter for "roller": t = {'r': 2, 'o': 1, 'l': 2, 'e': 1}
• Update cnt by taking minimum frequencies:
  • 'b': min(1, 0) = 0 (no 'b' in "roller")
  • 'e': min(1, 1) = 1
  • 'l': min(2, 2) = 2
  • 'a': min(1, 0) = 0 (no 'a' in "roller")
• After processing: cnt = {'b': 0, 'e': 1, 'l': 2, 'a': 0}

Step 4: Generate result

• Call cnt.elements() which yields each character based on its count
• Characters with count 0 ('b' and 'a') are not included
• 'e' appears once, 'l' appears twice
• Result: ['e', 'l', 'l']

The output correctly shows that only 'e' and 'l' appear in all three words, with 'l' appearing at least twice in each word, so it appears twice in the result.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × m) where n is the number of words in the array and m is the average length of each word. More precisely, it can be written as O(n × Σwᵢ) where Σwᵢ represents the sum of all word lengths.

• Creating the initial Counter for words[0] takes O(w₀) time where w₀ is the length of the first word
• The loop iterates through n-1 remaining words
• For each word, creating a Counter takes O(wᵢ) time
• The inner loop iterates through at most 26 characters (the size of the character set |Σ|) in cnt, and each min operation is O(1)
• Converting the Counter to a list using elements() takes O(k) where k is the total count of common characters, which is bounded by the length of the shortest word

Therefore, the total time complexity is O(w₀ + Σᵢ₌₁ⁿ⁻¹(wᵢ + |Σ|) + k) which simplifies to O(n × Σwᵢ) since the character set size |Σ| = 26 is constant.

Space Complexity: O(|Σ|) where |Σ| is the size of the character set, which equals 26 for lowercase English letters.

• The Counter cnt stores at most 26 unique characters (lowercase English letters)
• The temporary Counter t also stores at most 26 unique characters
• The output list size depends on the result but is bounded by the input

Since the character set size is constant at 26, the space complexity is O(1) in practical terms, but more formally expressed as O(|Σ|) or O(26).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Modifying the Counter While Iterating

A common mistake is trying to remove characters from the counter while iterating over it:

Incorrect Approach:

for w in words[1:]:
    t = Counter(w)
    for c in cnt:
        if c not in t:
            del cnt[c]  # RuntimeError: dictionary changed size during iteration
        else:
            cnt[c] = min(cnt[c], t[c])

Why it fails: Modifying a dictionary (or Counter) while iterating over it causes a RuntimeError in Python.

Correct Solution: Let the minimum operation handle it naturally. When a character doesn't exist in the current word, t[c] returns 0, so min(cnt[c], t[c]) becomes 0, effectively removing that character from the final result.

Pitfall 2: Not Handling Empty Word Arrays

If the input array is empty, accessing words[0] will raise an IndexError:

Incorrect Approach:

def commonChars(self, words: List[str]) -> List[str]:
    cnt = Counter(words[0])  # IndexError if words is empty
    # ...

Correct Solution: Add a guard clause:

def commonChars(self, words: List[str]) -> List[str]:
    if not words:
        return []
    cnt = Counter(words[0])
    # ...

Pitfall 3: Using Set Intersection Instead of Frequency Counting

Some might try to use set operations, which loses frequency information:

Incorrect Approach:

def commonChars(self, words: List[str]) -> List[str]:
    common = set(words[0])
    for w in words[1:]:
        common &= set(w)  # This loses frequency information
    return list(common)  # Wrong: returns ['l', 'e'] instead of ['l', 'l', 'e']

Why it fails: Sets only track unique elements, not their frequencies. If 'l' appears twice in all words, the set approach would only return one 'l'.

Correct Solution: Use Counter to maintain frequency information throughout the process.

Pitfall 4: Creating New Counter in Each Iteration

Creating a new counter for cnt in each iteration instead of updating it in-place:

Inefficient Approach:

for w in words[1:]:
    t = Counter(w)
    new_cnt = Counter()
    for c in cnt:
        new_cnt[c] = min(cnt[c], t[c])
    cnt = new_cnt  # Creates unnecessary new objects

Better Solution: Update the existing counter in-place to avoid unnecessary object creation and improve performance.