Find Common Characters - Solution & Explanation
Problem Statement
Given a string array words, return an array of all characters that show up in all strings within the words (including duplicates). You may return the answer in any order.
Example 1:
Input: words = ["bella","label","roller"] Output: ["e","l","l"]
Example 2:
Input: words = ["cool","lock","cook"] Output: ["c","o"]
Constraints:
1 <= words.length <= 1001 <= words[i].length <= 100words[i]consists of lowercase English letters.
Approach Overview
Problem Overview: You are given an array of lowercase strings. The goal is to return all characters that appear in every word, including duplicates. If a character appears twice in all strings, it must appear twice in the result.
Approach 1: Counting Characters with Maps (Time: O(n * k), Space: O(26))
This approach uses a hash map to track character frequencies for each word. Start by counting characters in the first word. Then iterate through the remaining words and update the counts by taking the minimum frequency for each character. If a character appears fewer times in another word, reduce the stored count accordingly. The final map represents the characters common across all words. This approach works well when using a hash table abstraction because it keeps the logic simple and easy to reason about.
After processing all strings, iterate through the map and append each character to the result as many times as its stored frequency. The key insight is that the minimum frequency of each character across all words determines how many times it appears in the answer.
Approach 2: Utilizing Frequency Arrays Directly (Time: O(n * k), Space: O(26))
Since all characters are lowercase English letters, a fixed-size frequency array of length 26 replaces the hash map. First compute the frequency array for the first string. Then iterate through the remaining words and compute a temporary frequency array for each word. Update the global array by taking the minimum value for every index.
This method avoids hash lookups and relies on direct index access, making it slightly faster in practice. For each character position i, the stored value represents the minimum number of times that character appears in every word. After processing all strings, iterate through the array and append characters to the result accordingly.
This technique is common in problems involving arrays and string frequency counting where the character set is small and fixed. Using arrays keeps memory predictable and operations constant time.
Recommended for interviews: The frequency array approach is usually preferred. It demonstrates awareness of constraints (only 26 lowercase letters) and reduces overhead compared to hash maps. The map-based approach still shows solid understanding of frequency counting and works well if the character set were larger or unknown.
Approach 1: Approach 1: Counting Characters with Maps
In this approach, we will use a hash map (or dictionary) to store the frequency of each character for each word. We then update a common frequency count table that holds the minimum frequency of each character across all words. This ensures that only characters existing in all words are recorded.
This C solution initializes two arrays of size 26 (for each letter of the alphabet) to count occurrences. It iterates over each word, updates character counts, and then calculates the minimum count for each character.
Complexity
Time Complexity: O(N*K) where N is the number of words and K is the average length of the words. Space Complexity: O(1) since the space does not scale with input size.
Approach 2: Approach 2: Utilizing Frequency Arrays Directly
We can alternatively use direct character arrays to represent frequencies and update these arrays with each subsequent word processed. Starting with the first word's character frequencies, we iteratively compute the minimum with the rest.
In this C implementation, we use frequency arrays to compute the minimum occurrence of each character across all words. Frequency is updated per word using a temporary array and merged via a minimum operation.
Complexity
Time Complexity: O(N*K). Space Complexity: O(1) for constant sized arrays.
Approach 3: Counting
We use an array cnt of length 26 to record the minimum number of times each character appears in all strings. Finally, we traverse the cnt array and add characters with a count greater than 0 to the answer.
The time complexity is O(n sum w_i), and the space complexity is O(|\Sigma|). Here, n is the length of the string array words, w_i is the length of the i-th string in the array words, and |\Sigma| is the size of the character set, which is 26 in this problem.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Approach 1: Counting Characters with Maps | Time Complexity: O(N*K) where N is the number of words and K is the average length of the words. Space Complexity: O(1) since the space does not scale with input size. |
| Approach 2: Utilizing Frequency Arrays Directly | Time Complexity: O(N*K). Space Complexity: O(1) for constant sized arrays. |
| Counting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Counting Characters with Maps | O(n * k) | O(26) | General solution when using hash maps or when character set size may vary |
| Frequency Arrays Directly | O(n * k) | O(26) | Best choice when characters are limited to lowercase letters and constant-time indexing is preferred |
Video Solution
LeetCode Find Common Characters Solution Explained - Java • Nick White • 22,057 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Find Common Characters easy or hard?
Find Common Characters Python/Java solution
How to solve Find Common Characters in O(n)?
What is the best approach for Find Common Characters?
Is Find Common Characters asked at Google/Amazon/Meta?
What data structure is used in Find Common Characters?
What is the time complexity of Find Common Characters?
Ready to solve this problem?
Practice Find Common Characters with our built-in code editor and test cases.
Practice on FleetCode