1044. Find Common Characters

• Difficulty: Easy

• Topics: Array, Hash Table

• Similar Questions:

  • Intersection of Two Arrays II

Problem:

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates).  For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.

You may return the answer in any order.

Example 1:

Input: ["bella","label","roller"]
Output: ["e","l","l"]

Example 2:

Input: ["cool","lock","cook"]
Output: ["c","o"]

Note:

1. 1 <= A.length <= 100
2. 1 <= A[i].length <= 100
3. A[i][j] is a lowercase letter

Solutions:

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        if (A.size() == 0)  return {};

        vector<int> common = countFreq(A[0]);
        for (int i = 1; i < A.size(); ++i) {
            vector<int> freq = countFreq(A[i]);
            for (int j = 0; j < 26; ++j) {
                common[j] = min(common[j], freq[j]);
            }
        }

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

        return ret;  
    }

private:
    vector<int> countFreq(const string& str) {
        vector<int> freq(26, 0);
        for (auto& c : str) {
            ++freq[c - 'a'];
        }

        return freq;
    }

};