1002. Find Common Characters

EasyArrayHash TableString
Leetcode Link

Problem Description

The given problem requires us to find the common characters across all strings in the given array of strings words. The characters need to be counted with their frequency, which means if a character appears twice in all strings, it should appear twice in the resulting array. The characters in the resulting array can be in any order, and we need to take into account duplicates as well.

Intuition

To solve this problem, we can take the following approach:

  1. Start with counting the frequency of characters in the first string. This gives us a starting point and includes all characters, as we are looking for characters that are common in all strings.

  2. Traverse through the remaining strings and, for each string:

    • Count the frequency of characters in the current string.
    • Compare the frequency of each character with the frequency in our current count (initialized from the first string).
    • Update the count to the minimum frequency found between the current count and the frequency in the current string. This step ensures that we only keep the count of characters that are common across all strings processed so far.
  3. Once we have the final count of characters that are common to all strings in words, we can create our resulting array. We add each character to the array based on the frequency recorded in our count.

By following these steps, we collect the common characters across all strings efficiently with the consideration of their frequency.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece:

A person thinks of a number between 1 and 1000. You may ask any number questions to them, provided that the question can be answered with either "yes" or "no".

What is the minimum number of questions you needed to ask so that you are guaranteed to know the number that the person is thinking?

Solution Approach

The implementation begins by using a Counter from the collections module in Python, which is a subclass of dict. It's specifically designed to count hashable objects, in our case, characters in a string.

Here's the step-by-step breakdown of the code:

  1. Initialize the counter with the characters of the first word:

    1cnt = Counter(words[0])

    This gives us a dictionary-like object where keys are characters and values are their frequencies in the first string.

  2. Iterate over all the other words in the words list:

    1for w in words:
    2    ccnt = Counter(w)

    For each word w, we create its character counter ccnt.

  3. For every character in cnt (which contains the character count from the first word), we take the minimum frequency found in both the cnt and the character counter for the current word ccnt:

    1for c in cnt.keys():
    2    cnt[c] = min(cnt[c], ccnt[c])

    This step essentially updates cnt so that it only contains characters that are present in every word encountered so far and in the smallest frequency among them. It's the intersection part of the algorithm.

  4. After iterating through all the strings and updating the counter, we have our final cnt which includes only the common characters. Lastly, we need to convert this count into a list of characters.

    1ans = []
    2for c, v in cnt.items():
    3    ans.extend([c] * v)

    For each character and its count in cnt, we extend our answer list ans with that character repeated v times. This repeats a character as many times as it appears in all strings.

This solution ensures that we only keep characters that are common to all words and respects their minimum frequency across the words. The use of Counter and dictionary operations makes the implementation concise and efficient.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example Walkthrough

Let's walk through a small example to understand the solution approach presented. Suppose our words array is:

1words = ["bella", "label", "roller"]

We want to find the common characters across all these words, with their exact frequency. Let's apply our intuition step by step:

Step 1: First Word's Characters We initialize the counter with the first word bella. The counter would be something like this:

1cnt = Counter("bella")  # cnt is {'b': 1, 'e': 1, 'l': 2, 'a': 1}

Step 2: Traverse Remaining Words Now we go through the other words in the list: "label" and "roller". Let's take them one by one.

  • For the second word, label:

    1ccnt = Counter("label")  # ccnt is {'l': 2, 'a': 1, 'b': 1, 'e': 1}
  • Now for every character in our initial counter cnt, we update the counts to the minimum we find in ccnt. For the 'l' character, both counters have a count of 2, so we keep it as 2 in cnt. We do the same for other characters:

    1# After updating with 'label'
    2cnt = {'b': 1 ('bella' had 1, 'label' had 1), 
    3       'e': 1 ('bella' had 1, 'label' had 1),
    4       'l': 2 ('bella' had 2, 'label' had 2),
    5       'a': 1 ('bella' had 1, 'label' had 1)}
  • Next, for the third word, roller:

    1ccnt = Counter("roller")  # ccnt is {'r': 2, 'o': 1, 'l': 2, 'e': 1}
  • We again update the cnt to keep only the minimum count for each character found in both counters:

    1# After updating with 'roller'
    2cnt = {'b': 0 ('bella' had 1, 'roller' had 0), 
    3       'e': 1 ('bella' had 1, 'roller' had 1),
    4       'l': 2 ('bella' had 2, 'roller' had 2),
    5       'a': 0 ('bella' had 1, 'roller' had 0)}

Characters 'b' and 'a' are not present in 'roller', so their count is updated to zero.

Step 3: Building the Result Array Finally, we create the resulting array by adding each character from cnt its counted number of times:

1ans = []
2for c, v in cnt.items():
3    ans.extend([c] * v)  # ['e', 'l', 'l']

After traversing all the strings and updating the counter, we only kept 'e' and 'l', each character appearing respectively once and twice, since those are the only ones common to all the strings in the exact minimum frequency.

Conclusively, our resulting array for common characters across all strings in words would be:

1['e', 'l', 'l']

This illustrates how the described algorithm works to find common characters among an array of strings taking into account their frequency.

Not Sure What to Study? Take the 2-min Quiz:

How would you design a stack which has a function min that returns the minimum element in the stack, in addition to push and pop? All push, pop, min should have running time O(1).

Python Solution

1from collections import Counter  # Importing Counter class from collections module
2
3class Solution:
4    def commonChars(self, words: List[str]) -> List[str]:
5        # Initialize a Counter for the first word to keep track of letter frequencies
6        char_count = Counter(words[0])
7      
8        # Iterate through all words in the input list
9        for word in words:
10            # Create a Counter for the current word
11            current_count = Counter(word)
12          
13            # Check all the characters in the initial word's counter
14            for char in list(char_count):
15                # Update the character's count to be the minimum of the current and the first word's count
16                # This ensures we only keep as many of a character as is common to all words so far
17                char_count[char] = min(char_count[char], current_count[char])
18      
19        # Initialize an empty list to hold the common characters
20        common_characters = []
21      
22        # Iterate through the items in the final char_count
23        for char, count in char_count.items():
24            # For each character, add it to the list as many times as its count
25            common_characters.extend([char] * count)
26      
27        # Return the list of common characters
28        return common_characters
29

Java Solution

1import java.util.List;
2import java.util.Arrays;
3import java.util.ArrayList;
4
5class Solution {
6    public List<String> commonChars(String[] words) {
7        // Initialize a count array to track the minimum frequency of each letter
8        int[] letterCount = new int[26];
9      
10        // Start by setting each letter's frequency to a high value
11        Arrays.fill(letterCount, Integer.MAX_VALUE);
12      
13        // Iterate over each word in the input array
14        for (String word : words) {
15            // Initialize a temporary array to store the frequency of each letter in the current word
16            int[] currentWordCount = new int[26];
17            // Loop through each character in the current word and increment its frequency
18            for (int i = 0; i < word.length(); ++i) {
19                currentWordCount[word.charAt(i) - 'a']++;
20            }
21            // Update the letterCount array to keep the minimum frequency among the words processed so far
22            for (int i = 0; i < 26; ++i) {
23                letterCount[i] = Math.min(letterCount[i], currentWordCount[i]);
24            }
25        }
26
27        // Prepare the result list
28        List<String> result = new ArrayList<>();
29      
30        // Add the common characters to the result list, based on the letterCount frequencies
31        for (int i = 0; i < 26; ++i) {
32            while (letterCount[i] > 0) {
33                // Append the character to the result list
34                result.add(String.valueOf((char) (i + 'a')));
35                // Decrement the count for this letter
36                letterCount[i]--;
37            }
38        }
39        return result;
40    }
41}
42

C++ Solution

1class Solution {
2public:
3    vector<string> commonChars(vector<string>& words) {
4        // Initialize a count array for 26 letters with a high number to represent infinity.
5        int letterCount[26];
6        memset(letterCount, 0x3f, sizeof(letterCount));
7
8        // Loop through each word in the words vector.
9        for (const auto& word : words) {
10            // Local count for letters in the current word.
11            int wordLetterCount[26] = {0};
12          
13            // Count each letter in the current word.
14            for (char letter : word) {
15                ++wordLetterCount[letter - 'a'];
16            }
17
18            // Compare counts for each letter with the global count and take the minimum.
19            for (int i = 0; i < 26; ++i) {
20                letterCount[i] = min(letterCount[i], wordLetterCount[i]);
21            }
22        }
23
24        // Prepare the result vector to store common letters.
25        vector<string> result;
26        for (int i = 0; i < 26; ++i) {
27            // Add the appropriate number of the current letter to the result.
28            while (letterCount[i] > 0) {
29                result.emplace_back(1, static_cast<char>(i + 'a'));
30                --letterCount[i];
31            }
32        }
33
34        return result; // Return the final result.
35    }
36};
37

Typescript Solution

1function commonChars(words: string[]): string[] {
2  // Initialize a frequency array to keep track of each character's minimum occurrence across all words
3  const minFrequencies: number[] = new Array(26).fill(Infinity);
4
5  // Iterate over each word in the input array
6  for (const word of words) {
7    // Temporary frequency array for the current word
8    const wordFrequencies: number[] = new Array(26).fill(0);
9
10    // Populate the frequency array for the current word
11    for (const char of word) {
12      const charIndex = char.charCodeAt(0) - 'a'.charCodeAt(0);
13      wordFrequencies[charIndex]++;
14    }
15
16    // Update the minFrequencies array with the minimum frequency of each character
17    for (let i = 0; i < 26; ++i) {
18      minFrequencies[i] = Math.min(minFrequencies[i], wordFrequencies[i]);
19    }
20  }
21
22  // The result array to hold common characters
23  const result: string[] = [];
24
25  // Build the result array using characters that appear across all words based on min frequencies
26  for (let i = 0; i < 26; ++i) {
27    // Continue appending the character to the result as long as the frequency is greater than 0
28    while (minFrequencies[i] > 0) {
29      result.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
30      minFrequencies[i]--;
31    }
32  }
33
34  return result; // Return the array containing all common characters
35}
36
Fast Track Your Learning with Our Quick Skills Quiz:

What is the worst case running time for finding an element in a binary tree (not necessarily binary search tree) of size n?

Time and Space Complexity

The given code snippet defines a function commonChars in the Solution class, which finds common characters among all strings in a given list.

Time Complexity:

Let n be the number of strings in the words list and k be the average length of these strings.

  1. We initialize a counter cnt with the first word in the list, which takes O(k) time.
  2. Then, we iterate over each word in the words list:
    • For each word, we initialize a counter ccnt, which also takes O(k) time.
    • We iterate over each key in cnt to update it with the minimum frequency found in ccnt, and since cnt never has more characters than there are in the alphabet, let's denote the alphabet size as a, and this nested loop runs in O(a) time for each word.

Overall, the time complexity looks like this:

For the loop over words: n * (O(k) + O(a)) We take O(a) from inside as it is constant and does not depend on n or k.

Since O(a) is constant and typically a <= 26 (for English alphabet), we can simplify the expression:

So, the total time complexity is: O(n*k + n*a) which simplifies to O(n*k) because n*k will typically dominate n*a.

Space Complexity:

  1. The counter cnt uses O(a) space.
  2. For each word, a temporary counter ccnt is created, which also uses O(a) space, however since it is not preserved after each iteration, it doesn't add up with the space complexity.
  3. The answer list ans in the worst case can contain all characters from all strings if all characters are the same which is O(n*k).

Thus the total space complexity is O(a + n*k). Since a is a constant and typically a <= 26, the main factor here is n*k.

In conclusion, the space complexity of the code is O(n*k) (since we're considering the space for the output, which can be as large as the input in the worst case).

Learn more about how to find time and space complexity quickly.


Recommended Readings


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫