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
Aof strings, where each string consists only of lowercase letters. - The length of
Ais 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.
-
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.
-
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
- Initialize a hash table
char_countwith keys as characters from ‘a’ to ‘z’ and values set to zero. - Populate
char_countwith the frequency of each character in the first string. - For each subsequent string, create a temporary hash table
temp_countto store its character frequencies. - Update
char_countby taking the minimum value between the current count and the count fromtemp_count. - 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.