Find Common Characters - Video Solutions

Problem Overview: You are given an array of lowercase strings. The goal is to return all characters that appear in every word, including duplicates. If a character appears twice in all strings, it must appear twice in the result.

Approach 1: Counting Characters with Maps (Time: O(n * k), Space: O(26))

This approach uses a hash map to track character frequencies for each word. Start by counting characters in the first word. Then iterate through the remaining words and update the counts by taking the minimum frequency for each character. If a character appears fewer times in another word, reduce the stored count accordingly. The final map represents the characters common across all words. This approach works well when using a hash table abstraction because it keeps the logic simple and easy to reason about.

After processing all strings, iterate through the map and append each character to the result as many times as its stored frequency. The key insight is that the minimum frequency of each character across all words determines how many times it appears in the answer.

Approach 2: Utilizing Frequency Arrays Directly (Time: O(n * k), Space: O(26))

Since all characters are lowercase English letters, a fixed-size frequency array of length 26 replaces the hash map. First compute the frequency array for the first string. Then iterate through the remaining words and compute a temporary frequency array for each word. Update the global array by taking the minimum value for every index.

This method avoids hash lookups and relies on direct index access, making it slightly faster in practice. For each character position i, the stored value represents the minimum number of times that character appears in every word. After processing all strings, iterate through the array and append characters to the result accordingly.

This technique is common in problems involving arrays and string frequency counting where the character set is small and fixed. Using arrays keeps memory predictable and operations constant time.

Recommended for interviews: The frequency array approach is usually preferred. It demonstrates awareness of constraints (only 26 lowercase letters) and reduces overhead compared to hash maps. The map-based approach still shows solid understanding of frequency counting and works well if the character set were larger or unknown.