Find Common Characters in All Strings
Problem
Given an array of strings words, return a list of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.
- 1 ≤ words.length ≤ 100
- 1 ≤ words[i].length ≤ 100
- words[i] consists of lowercase English letters.
Example
words = ["bella","label","roller"]["e","l","l"]Start by counting characters in the first word: 'b':1, 'e':1, 'l':2, 'a':1. For the second word, count characters and update the common counts by taking the minimum count for each character. For example, 'l' appears twice in both 'bella' and 'label', so it remains 2. After processing all words, the characters with positive counts are 'e' and 'l' twice, which are returned as ['e', 'l', 'l'].
Approach
Straightforward Solution
A brute-force approach would check each character against every word, counting occurrences repeatedly, resulting in inefficient repeated scans and higher time complexity.
Core Observation
The problem reduces to finding the intersection of character counts across all strings. Each character's count in the final result is the minimum count it appears in any word.
Path to Optimal
PreviewBy using a hash map (Counter) to store character frequencies of the first word, then iteratively intersecting with the frequency counts of subsequent words by taking the minimum counts, the algorithm efficiently narrows down the common characters…
Full step-by-step walkthrough on Pro →
Optimal Approach
PreviewInitialize a Counter with the first word's character counts. For each subsequent word, create a Counter and update the main Counter by taking the minimum counts for each character…
Full step-by-step walkthrough on Pro →
Want the full reasoning chain?
Unlock the complete walkthrough, line-by-line analysis, and recall drill.
Unlock ProTime
O(N * M)
Each of the N words is processed once, and counting characters in each word takes O(M) time. Updating the common counts involves iterating over the keys of the current common_counts, which is at most 26 for lowercase letters, so effectively constant. Overall complexity is dominated by counting characters in all words.
Space
O(1)
The auxiliary space is O(1) because the character set is limited to lowercase English letters (26), so the Counters store at most 26 keys. The output list size depends on the input but is not counted as auxiliary space.
Pattern Spotlight
Hash Maps (Frequency Intersection)
When finding common elements with counts across multiple collections, maintain a frequency map of the first collection and iteratively intersect it with subsequent collections by taking minimum counts, effectively narrowing down to the shared elements.
Solution
| 1 | from collections import Counter |
| 2 | |
| 3 | class Solution: |
| 4 | def commonChars(self, words: List[str]) -> List[str]: |
| 5 | common_counts = Counter(words[0]) |
| 6 | |
| 7 | for word in words[1:]: |
| 8 | word_counts = Counter(word) |
| 9 | |
| 10 | for char in list(common_counts.keys()): |
| 11 | common_counts[char] = min(common_counts[char], word_counts[char]) |
| 12 | |
| 13 | common_chars = [] |
| 14 | |
| 15 | for char, count in common_counts.items(): |
| 16 | for _ in range(count): |
| 17 | common_chars.append(char) |
| 18 | |
| 19 | return common_chars |
Step-by-Step Solution
Initialize Common Character Counts from First Word
| 5 | common_counts = Counter(words[0]) |
Objective
To establish a baseline frequency map of characters from the first word to compare against all others.
Key Insight
Starting with the first word's character counts provides a reference frequency map. This map represents the maximum possible counts for each character that can appear in the final result. Subsequent words will only reduce these counts, never increase them, ensuring correctness.
Interview Quick-Check
Core Logic
Using a Counter on the first word sets the initial frequency counts, which will be intersected with counts from other words.
Common Pitfalls & Bugs
Failing to initialize from the first word or starting with an empty map would complicate the intersection logic and could lead to incorrect counts.
Iteratively Intersect Character Counts with Subsequent Words
To update the common character counts by taking the minimum frequency for each character across all words.
Construct the Result List from Final Common Counts
To build the output list by repeating each character according to its final minimum count.
Return the List of Common Characters
To output the final list of characters common to all words.
3 more steps with full analysis available on Pro.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
common_counts[char] = min(common_counts[char], word_counts[char])Update the count for each character to the minimum between current common count and current word count.
Taking the minimum count ensures that only characters appearing in all words with their lowest frequency are retained, which is the core logic for finding common characters including duplicates.
common_counts = Counter(words[0])Initialize a Counter with character frequencies from the first word.
This line sets the initial frequency baseline for all characters, which subsequent words will intersect with to find common characters.
Full line-by-line criticality + rationale for all 10 lines available on Pro.
Test Your Understanding
Why is taking the minimum count of each character across all words the correct way to find common characters including duplicates?
See the answer with Pro.
Related Problems
Hash Maps pattern
Don't just read it. Drill it.
Reconstruct Find Common Characters in All Strings from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Find Common Characters in All Strings drill