We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find Common Characters

Difficulty: Easy

Problem Description

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.

Key Insights

  • Each character must appear in all strings.
  • Count the frequency of each character in each string.
  • The minimum frequency across all strings determines how many times that character should appear in the result.

Space and Time Complexity

Time Complexity: O(N * M), where N is the number of strings and M is the average length of the strings.
Space Complexity: O(1), since we are only using a fixed-size array to count characters (26 lowercase English letters).

Solution

To solve the problem, we will:

  1. Utilize a list of size 26 (for each letter in the English alphabet) to maintain the minimum frequency of each character across all strings.
  2. Iterate through each string and count the frequency of characters using a temporary list.
  3. Update the minimum frequency list by comparing with the current string's frequencies.
  4. Construct the result based on the minimum frequency list.

Code Solutions

def commonChars(words):
    # Initialize a list to keep track of minimum frequency of each character
    min_freq = [float('inf')] * 26
    
    for word in words:
        # Create a frequency count for the current word
        curr_freq = [0] * 26
        for char in word:
            curr_freq[ord(char) - ord('a')] += 1
        
        # Update min_freq with the minimum found so far
        for i in range(26):
            min_freq[i] = min(min_freq[i], curr_freq[i])
    
    # Build the result using the min_freq
    result = []
    for i in range(26):
        result.extend([chr(i + ord('a'))] * min_freq[i])
    
    return result
← Back to All Questions