Domain 1EasyCORE

Find Common Characters

The problem requires finding all characters that appear in every string within an array of strings. The output should include duplicates based on their minimum frequency across all strings. For instance, if the character 'a' appears three times in each string, it should be included three times in the result.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array#Hash Table

1002. Find Common Characters

Model: qwen2.5-coder:14b
Topics: Array,Hash Table
FAANG asked: 1
Acceptance rate: 68.7%


Problem Breakdown

The problem requires finding all characters that appear in every string within an array of strings. The output should include duplicates based on their minimum frequency across all strings. For instance, if the character ‘a’ appears three times in each string, it should be included three times in the result.

Inputs:

  • An array A of strings, where each string consists only of lowercase letters.
  • The length of A is between 1 and 100.
  • Each string’s length is also between 1 and 100.

Outputs:

  • A list of characters that appear in all strings within the array, including duplicates based on their minimum frequency across all strings.

Implicit Constraints or Tricky Edge Cases:

  • The input array can contain only one string.
  • Strings can be empty (though this is not possible given the constraints).
  • Characters are always lowercase letters.

Intuition

A brute-force approach would involve checking each character in every string, which could lead to a high time complexity. Instead, we can leverage hash tables to efficiently count occurrences of each character across all strings and then determine the common characters based on these counts.

  1. Brute Force Approach:

    • For each character in the first string, check if it exists in all other strings.
    • This approach is inefficient because it involves nested loops over the strings and characters.
  2. Key Insight:

    • Use a hash table to count occurrences of each character in the first string.
    • Iterate through the remaining strings, updating the counts to reflect the minimum frequency of each character across all strings.
    • Finally, construct the result list based on these updated counts.

Approach

  1. Initialize a hash table char_count with keys as characters from ‘a’ to ‘z’ and values set to zero.
  2. Populate char_count with the frequency of each character in the first string.
  3. For each subsequent string, create a temporary hash table temp_count to store its character frequencies.
  4. Update char_count by taking the minimum value between the current count and the count from temp_count.
  5. After processing all strings, construct the result list by repeating each character according to its count in char_count.

Complexity Analysis

  • Time Complexity: O(n * m), where n is the number of strings and m is the average length of a string. This is because we iterate through each string and each character within those strings.
  • Space Complexity: O(1) for the hash table, as it always contains 26 entries (one for each lowercase letter).

Solution

def commonChars(A):
    from collections import Counter
    
    # Initialize with counts from the first string
    char_count = Counter(A[0])
    
    # Iterate over the remaining strings
    for i in range(1, len(A)):
        temp_count = Counter(A[i])
        # Update char_count to keep only the minimum count of each character
        for char in char_count:
            char_count[char] = min(char_count[char], temp_count[char])
    
    # Construct the result list based on the final counts
    result = []
    for char, count in char_count.items():
        result.extend([char] * count)
    
    return result

Edge Cases Handled

  • Single String: If the input array contains only one string, the function will return all characters from that string.
  • All Strings Identical: If all strings are identical, the function will return all characters from any of those strings.
  • No Common Characters: If there are no common characters across all strings, the function will return an empty list.