LeetCode Solutions Blog

Find Common Characters

Number: 1044

Difficulty: Easy

Paid? No

Problem Description

Given an array of strings, the goal is to return an array containing all the characters that appear in every string in the input array (including duplicates). For example, if a character appears twice in every string, it should appear twice in the output.

Key Insights

Use frequency counting for characters.
Determine the minimum count for each character across all words.
Use the minimum frequency to determine how many times a character appears in every string.
The order of the characters in the resulting list does not matter.

Space and Time Complexity

Time Complexity: O(m * n) where m is the number of words and n is the average length of the words. Space Complexity: O(1) since the count arrays are of fixed size (26 for the alphabet).

Solution

We maintain a global frequency count for each of the 26 lowercase English letters. Initially, set the count for each letter to a very high number (or use the frequency of the first word). For each subsequent word, compute the frequency of each letter and update the global frequency by taking the minimum frequency encountered so far for each letter. Finally, traverse the frequency array and add each character to the result the number of times it appears (i.e., its minimum frequency across all words).

Code Solutions

# Python solution to find common characters
from collections import Counter

def commonChars(words):
    # Initialize global frequency with frequency count of the first word
    common_frequency = Counter(words[0])
    
    # Update the global frequency with the minimum frequency found in each word
    for word in words[1:]:
        # Compute frequency of current word
        word_frequency = Counter(word)
        # Update common_frequency to be the minimum occurrence of each character
        for char in list(common_frequency.keys()):
            common_frequency[char] = min(common_frequency[char], word_frequency.get(char, 0))
            # Remove character if it does not appear in current word
            if common_frequency[char] == 0:
                del common_frequency[char]
    
    # Build the result list based on the frequency of each character
    result = []
    for char, count in common_frequency.items():
        result.extend([char] * count)
    
    return result

# Example usage:
print(commonChars(["bella","label","roller"]))