Find Common Characters

Problem  Statement

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.

Examples

Example 1:

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

Explanation: The characters 'e' and 'l' appear in all strings, with 'l' appearing twice in each.

Example 2:

Input: words = ["coo", "lock", "cook"]
Output: ["c", "o"]

Explanation: Both 'c' and 'o' appear in all strings, and no character appears more times than they do in each string.

Example 3:

Input: words = ["hello", "goodbye", "welcome"]
Output: []

Explanation: There is no character that appears in all three strings, so the output is an empty array.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 100
• words[i] consists of lowercase English letters.

Different Approaches

1️⃣  Hashing

Intuition:

1. Initialize Two Frequency Arrays:
   • Create a common array of size 26 (for each letter from 'a' to 'z') and initialize it with INT_MAX. This array will store the minimum frequency of each character across all strings.
   • Use a temp array, also of size 26, which will be used to count the frequency of characters in each string during iteration.
2. Process Each String in the Input Vector:
   • For each string in the vector, reset temp to zero, then count the frequency of each character in the current string and store it in temp.
   • After counting, update the common array by setting each element to the minimum of the corresponding elements in common and temp. This step ensures that common holds the minimum occurrence of each character across all strings seen so far.
3. Construct the Result:
   • After processing all strings, common will contain the minimum frequency of each character across all strings.
   • For each character in common, add it to the result the number of times specified by its count in common.

Dry Run:

words = ["bella", "label", "roller"]

         +-----+-----+-----+-----+-----+
common = | MAX | MAX | MAX | MAX | MAX |...
         +-----+-----+-----+-----+-----+
            0     1     2     3     4   ... 25
            a     b     c     d     e   ... z

Iterate over the words array:

First Word "bella"
       +---+---+---+---+---+---+---+---+
temp = | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |...
       +---+---+---+---+---+---+---+---+
         0   1   2   3   4   5   6   7  ... 25
         a   b   c   d   e   f   g   h  ... z
         
Populate the frequency of first word characters in
temp character hash array.

temp would become
       +---+---+---+---+---+---+   +---+   +---+
temp = | 1 | 1 | 0 | 0 | 1 | 0 |...| 2 |...| 0 |
       +---+---+---+---+---+---+   +---+   +---+
         0   1   2   3   4   5       11  ... 25
         a   b   c   d   e   f       l   ... z

Update common for each character in common[i] = min(common[i], temp[i])

         +---+---+---+---+---+---+   +---+   +---+
common = | 1 | 1 | 0 | 0 | 1 | 0 |...| 2 |...| 0 |
         +---+---+---+---+---+---+   +---+   +---+
           0   1   2   3   4   5       11 ... 25
           a   b   c   d   e   f       l  ... z

Second Word "label"
       +---+---+---+---+---+---+---+---+   +---+
temp = | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |...| 0 |
       +---+---+---+---+---+---+---+---+   +---+
         0   1   2   3   4   5   6   7  ... 25
         a   b   c   d   e   f   g   h  ... z
         
Populate the frequency of second word characters in
temp character hash array.

temp would become
       +---+---+---+---+---+---+   +---+   +---+
temp = | 1 | 1 | 0 | 0 | 1 | 0 |...| 2 |...| 0 |
       +---+---+---+---+---+---+   +---+   +---+
         0   1   2   3   4   5       11  ... 25
         a   b   c   d   e   f       l   ... z

Update common for each character in common[i] = min(common[i], temp[i])

         +---+---+---+---+---+---+   +---+   +---+
common = | 1 | 1 | 0 | 0 | 1 | 0 |...| 2 |...| 0 |
         +---+---+---+---+---+---+   +---+   +---+
           0   1   2   3   4   5       11 ... 25
           a   b   c   d   e   f       l  ... z

Third Word "roller"
       +---+---+---+---+---+---+---+---+   +---+
temp = | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |...| 0 |
       +---+---+---+---+---+---+---+---+   +---+
         0   1   2   3   4   5   6   7  ... 25
         a   b   c   d   e   f   g   h  ... z
         
Populate the frequency of second word characters in
temp character hash array.

temp would become
       +---+---+---+---+---+   +---+   +---+   +---+
temp = | 0 | 0 | 0 | 0 | 1 |...| 2 |...| 2 |...| 0 |
       +---+---+---+---+---+   +---+   +---+   +---+
         0   1   2   3   4      11       17 ... 25
         a   b   c   d   e      l        r  ... z

Update common for each character in common[i] = min(common[i], temp[i])

         +---+---+---+---+---+---+   +---+   +---+
common = | 0 | 0 | 0 | 0 | 1 | 0 |...| 2 |...| 0 |
         +---+---+---+---+---+---+   +---+   +---+
           0   1   2   3   4   5       11 ... 25
           a   b   c   d   e   f       l  ... z

Construct the result:

common character hash array contains the minimum frequency of each character across all words.

For each index i, if common[i] is greater than zero, we add the character 'a' + i to the result common[i] times.
'e' appears once, so add "e".
'l' appears twice, so add "l" and "l".

Output:

["e", "l", "l"]

Code:

class Solution {
public:
    vector<string> commonChars(vector<string>& A) {
        // Initialize an array of 26 integers to keep track of the number of times
        // each character appears in all of the strings
        vector<int> chars(26, INT_MAX);
        
        // Iterate through all of the strings
        // Process each string in A
        for (string str : A) {
            // Initialize an array of 26 integers to keep track of the number of times
            // each character appears in the current string
            vector<int> curr(26, 0);
            
            // Iterate through the current string and update the array
            // Count each character in the current string.
            for (char c : str) {
                curr[c - 'a']++;
            }
            
            // Iterate through the array and update the global array
            for (int i = 0; i < 26; i++) {
                chars[i] = min(chars[i], curr[i]);
            }
        }
        
        // Initialize a vector of strings to store the common characters
        vector<string> res;
        
        // Iterate through the global array and add the common characters to the vector
        for (int i = 0; i < 26; i++) {
            for (int j = 0; j < chars[i]; j++) {
                res.push_back(string(1, 'a' + i));
            }
        }
        
        return res;
    }
};