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.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(N*K). Space Complexity: O(1) for constant sized arrays.
| 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. |
Longest Substring Without Repeating Characters - Leetcode 3 - Python • NeetCode • 657,697 views views
Watch 9 more video solutions →Practice Find Common Characters with our built-in code editor and test cases.
Practice on FleetCode