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
By 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. This approach avoids redundant counting and leverages fast dictionary operations.
Optimal Approach
Initialize 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. After processing all words, expand the final Counter into a list of characters repeated by their counts. This yields the common characters including duplicates in O(N * M) time, where N is the number of words and M is the average word length.
Time
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
| 7 | for word in words[1:]: |
| 8 | word_counts = Counter(word) |
| 10 | for char in list(common_counts.keys()): |
| 11 | common_counts[char] = min(common_counts[char], word_counts[char]) |
Objective
To update the common character counts by taking the minimum frequency for each character across all words.
Key Insight
By iterating over each subsequent word and counting its characters, the algorithm compares these counts with the current common counts. For each character, the minimum count is kept, effectively intersecting the sets of characters with their frequencies. This ensures that only characters present in all words with their minimum occurrence remain.
Interview Quick-Check
Core Logic
The intersection is performed by updating each character's count to the minimum between the current common count and the count in the current word.
State & Boundaries
Iterating over a list of keys from common_counts avoids runtime errors due to modifying the dictionary during iteration.
Common Pitfalls & Bugs
Not converting keys to a list before iteration can cause runtime errors because the dictionary size changes during updates.
Construct the Result List from Final Common Counts
| 13 | common_chars = [] |
| 15 | for char, count in common_counts.items(): |
| 16 | for _ in range(count): |
| 17 | common_chars.append(char) |
Objective
To build the output list by repeating each character according to its final minimum count.
Key Insight
After all intersections, the common_counts map holds the exact number of times each character appears in every word. Expanding this map into a list by repeating each character count times produces the final answer. This step translates the frequency map back into the required output format.
Interview Quick-Check
Core Logic
The final list is constructed by appending each character as many times as its count in the common_counts map.
Complexity
This step runs in O(1) time relative to character set size (max 26), but output size depends on input.
Return the List of Common Characters
| 19 | return common_chars |
Objective
To output the final list of characters common to all words.
Key Insight
Returning the constructed list completes the function, providing the caller with the characters that appear in all words including duplicates, fulfilling the problem requirements.
Interview Quick-Check
Core Logic
Returning the list completes the solution and matches the expected output format.
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.
word_counts = Counter(word)
Create a Counter for the current word's character frequencies.
Counting characters in the current word enables comparison with the existing common counts to update the intersection.
for char in list(common_counts.keys()):
Iterate over a list of keys from the common_counts dictionary.
Converting keys to a list prevents runtime errors caused by modifying the dictionary during iteration, ensuring safe updates.
for _ in range(count):
Repeat appending the character count times to the result list.
Appending each character multiple times according to its count ensures duplicates are correctly represented in the output.
for word in words[1:]:
Iterate over each word starting from the second word.
Processing each subsequent word allows the algorithm to refine the common character counts by intersecting with each word's character frequencies.
for char, count in common_counts.items():
Iterate over each character and its count in the common_counts map.
This loop translates the frequency map into individual characters repeated according to their counts, reconstructing the final result.
common_chars.append(char)
Append the character to the result list.
This line performs the actual insertion of each character instance into the output list, building the final answer.
return common_chars
Return the list of common characters.
Returning the constructed list completes the function, providing the correct output as specified by the problem.
common_chars = []
Initialize an empty list to store the final common characters.
This list will accumulate characters repeated by their final counts, preparing the output in the required format.
Test Your Understanding
Why is taking the minimum count of each character across all words the correct way to find common characters including duplicates?
Because a character can only appear in the final result as many times as it appears in every word. Taking the minimum count ensures that the character's frequency reflects the maximum number of times it can appear in all words simultaneously.
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