Find Common Characters

Difficulty: Easy | Acceptance: 74.70% | Paid: No Topics: Array, Hash Table, String

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.

• Examples
• Constraints
• Intersection of Counters
• Alphabet Iteration

Examples

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 <= 100
1 <= words[i].length <= 100
words[i] consists of lowercase English letters.

Intersection of Counters

Intuition We need to find the intersection of multisets (character counts) across all strings. We can maintain a global frequency array representing the minimum count of each character found so far and update it as we process each word.

Steps

• Initialize a frequency array min_freq of size 26 with a large value (e.g., infinity or counts of the first word).
• Iterate through each word in the input array.
• For each word, calculate its character frequency in a temporary array curr_freq.
• Update min_freq by taking the element-wise minimum between min_freq and curr_freq.
• After processing all words, convert the min_freq array back into a list of characters.

from typing import List

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        if not words:
            return []
        
        # Initialize with the first word's frequency
        min_freq = [float('inf')] * 26
        
        for word in words:
            curr_freq = [0] * 26
            for ch in word:
                curr_freq[ord(ch) - ord('a')] += 1
            
            # Update global minimum frequency
            for i in range(26):
                min_freq[i] = min(min_freq[i], curr_freq[i])
        
        # Construct result
        result = []
        for i in range(26):
            if min_freq[i] > 0:
                result.extend([chr(i + ord('a'))] * min_freq[i])
        
        return result

Complexity

• Time: O(N * M) where N is the number of words and M is the average length of a word.
• Space: O(1) auxiliary space (size 26 arrays), excluding the output list.
• Notes: This is the most efficient approach as it only requires constant extra space and a single pass through the characters of all words.

Alphabet Iteration

Intuition Since the input is constrained to lowercase English letters, we can iterate through the alphabet from ‘a’ to ‘z’. For each character, we count its occurrences in every word and take the minimum count.

Steps

• Initialize an empty result list.
• Loop through characters from ‘a’ to ‘z’.
• For each character, find the minimum frequency of that character across all words in the array.
• Append the character to the result list as many times as the minimum frequency.

from typing import List

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        result = []
        
        # Iterate through each character in the alphabet
        for i in range(26):
            char = chr(ord('a') + i)
            min_count = float('inf')
            
            # Find the minimum count of this char in all words
            for word in words:
                count = word.count(char)
                min_count = min(min_count, count)
                if min_count == 0:
                    break
            
            # Add the char to result min_count times
            result.extend([char] * min_count)
            
        return result

Complexity

• Time: O(26 * N * M) where N is the number of words and M is the average length of a word. Since 26 is a constant, this simplifies to O(N * M).
• Space: O(1) auxiliary space, excluding the output list.
• Notes: This approach is conceptually simple and leverages the fixed alphabet size constraint, though it may involve slightly more character comparisons than the single-pass frequency array method.