Find Common Characters

How it works

A character appears in all words only if it exists in every single word. Moreover, if a character appears twice in every word, we can include it twice in our result. The key insight is to track the minimum frequency of each character across all words. We start with the frequency counts from the first word, then for each subsequent word, we reduce each count to the minimum of the current count and that word's count.

Steps

1. Initialize a frequency array cnt of size 26 (for lowercase letters) with large values (or use the first word's counts).
2. For each word, count character frequencies in curCnt.
3. For each character, update cnt[c] = min(cnt[c], curCnt[c]).
4. Build the result by adding each character cnt[c] times.
5. Return the result list.

Complexity

• Time complexity: O(n * m)
• Space complexity:
  • O(1) extra space, since we have at most 26 different characters.
  • O(n * m) space for the output list.

Where n is the number of words and m is the length of the longest word.

Things to watch for

Initializing Counts to Zero Instead of Infinity

Starting the global frequency array with zeros causes min(0, curCnt[c]) to always be zero. Initialize with a large value or use the first word's counts as the starting point.

Adding Characters Once Instead of by Frequency

The result must include each common character as many times as it appears in all words. Appending each character only once ignores duplicates that appear in every word.

from typing import List
from collections import Counter

class Solution:
    def commonChars(self, words: List[str]) -> List[str]:
        cnt = Counter(words[0])

        for w in words:
            cur_cnt = Counter(w)
            for c in cnt:
                cnt[c] = min(cnt[c], cur_cnt[c])

        res = []
        for c in cnt:
            for i in range(cnt[c]):
                res.append(c)

        return res

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int> cnt(26, INT_MAX);

        for (string& word : words) {
            vector<int> curCnt(26, 0);
            for (char c : word) {
                curCnt[c - 'a']++;
            }

            for (int i = 0; i < 26; i++) {
                cnt[i] = min(cnt[i], curCnt[i]);
            }
        }

        vector<string> res;
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < cnt[i]; j++) {
                res.push_back(string(1, i + 'a'));
            }
        }

        return res;
    }
};