Find Common Characters in All Strings

Easy Hash Maps

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

Input: words = ["bella","label","roller"]
Output: ["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

1from collections import Counter
2
3class 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

1

Initialize Common Character Counts from First Word

5common_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.

2

Iteratively Intersect Character Counts with Subsequent Words

7for 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.

3

Construct the Result List from Final Common Counts

13common_chars = []
15for 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.

4

Return the List of Common Characters

19return 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.

Line 11 Critical
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.

Line 5 Critical
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.

Line 8 Core
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.

Line 10 Core
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.

Line 16 Core
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.

Line 7 Core
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.

Line 15 Core
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.

Line 17 Core
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.

Line 19 Standard
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.

Line 13 Standard
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

or drill a free problem