algoadvance

Given a list of strings words, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character appears 3 times in all strings but not 4 times, you need to include that character 3 times in the final answer.

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:

Clarifying Questions

  1. Are the strings always non-empty?
    • Yes, as per the given constraints.
  2. Should the order of characters in the output list matter?
    • No, the order does not matter as per the problem statement.
  3. Is it possible to have strings with no common characters?
    • Yes, in such cases, the output should be an empty list.

Strategy

  1. Count Characters in All Words: Utilize Python’s collections.Counter to count the frequency of characters in each string.
  2. Find Common Minimum Frequency: Initialize with the character count from the first word. Then, for each subsequent word, update this to keep only the minimum frequency of each character found so far.
  3. Construct Result: Convert the final character frequency map to a list containing the characters repeated according to their minimum frequency found in all strings.

Code

from collections import Counter
from typing import List

def commonChars(words: List<String]) -> List[str]:
    # Start with the character count of the first word
    common_count = Counter(words[0])
    
    # Update the common_count with the minimum counts found in subsequent words
    for word in words[1:]:
        word_count = Counter(word)
        for char in common_count.keys():
            if char in word_count:
                common_count[char] = min(common_count[char], word_count[char])
            else:
                common_count[char] = 0
    
    # Build the result list based on the final common_count
    result = []
    for char, count in common_count.items():
        result.extend([char] * count)
    
    return result

# Example usage:
words = ["bella", "label", "roller"]
print(commonChars(words))  # Output: ["e", "l", "l"]

Time Complexity

This approach should be efficient given the problem constraints, handling up to 10,000 character operations comfortably.

Try our interview co-pilot at AlgoAdvance.com