Problem of The Day: Find Common Characters

Problem Statement

Intuition

My first thought is to find the common characters among all words by leveraging frequency counts. By comparing the frequency of each character in every word, I can identify the minimum frequency of each character that appears in all words, ensuring that only the common characters are returned.

Approach

I will start by creating a list of frequency counters for each word. Then, I will use the first word’s frequency counter as a reference and compare it with the frequency counters of the remaining words. For each character in the reference counter, I will update its frequency to the minimum frequency found across all counters. If a character is not found in any of the other words, I will set its frequency to zero. Finally, I will construct the result list based on the updated frequencies of the characters.

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) because it always have a size of 26 (number of English alphabet)

Code

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        res = []
        counters = []
        for word in words:
            counters.append(Counter(word))

        w_count = counters[0]
        for c1, count in w_count.items():
            num_of_freq = count
            for freq in counters[1:]:
                if c1 in freq:
                    num_of_freq = min(num_of_freq, freq[c1])
                else:
                    w_count[c1] = 0
                    break
            else:
                w_count[c1] = num_of_freq

        for k, v in w_count.items():
            if v > 0:
                res += [k] * v

        return res

Editorial

class Solution:

    def commonChars(self, words: List[str]) -> List[str]:
        words_size = len(words)
        result = []

        # Initialize common_character_counts with the characters from the first word
        common_character_counts = collections.Counter(words[0])

        for i in range(1, words_size):
            # Count characters in the current word
            current_character_counts = collections.Counter(words[i])

            # Update the common character counts to keep the minimum counts
            for letter in common_character_counts.keys():
                common_character_counts[letter] = min(
                    common_character_counts[letter],
                    current_character_counts[letter],
                )

        # Collect the common characters based on the final counts
        for letter, count in common_character_counts.items():
            for _ in range(count):
                result.append(letter)

        return result