The Indian Engineer

Problem 1002 Find Common Characters

Posted on 2 mins

String Hash-Table Vector Array

Problem Statement

Link - Problem 1002

Question

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.

Example 1

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

Example 2

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

Constraints

Solution

class Solution {
public:
    vector<string> commonChars(vector<string>& words) {
        vector<int>baselineCount(26,0);
        string temp;
        for(int i =0;i<words[0].size();i++)
            {
                baselineCount[words[0][i]-'a']++;
            }
        for(auto word:words)
        {
            vector<int>newCount(26,0);
            for(const auto& ch:word)
                newCount[ch-'a']++;

            for(int i= 0;i<26;i++)
                baselineCount[i] = min(baselineCount[i],newCount[i]);
        }
        vector<string>answer;
        for(int i =0; i<26;i++)
        {
            while(baselineCount[i]--)
            {
                temp = "";
                temp += 'a'+i;
                answer.push_back(temp);
            }
        }
        return answer;


    }
};

Complexity Analysis

Explanation

1. Intuition

- We need to find the common characters in all the strings.
- We need some kind of hash table to store all the common characters.
- Characters may be repeated so we need to store the count of each character.

2. Implementation

- Initialize a vector `baselineCount` of size 26 with all elements as `0`.
- Iterate over the first word and increment the count of each character in the `baselineCount`.
- Iterate over all the words and for each word create a new vector `newCount` of size 26 with all elements as `0`.
- Increment the count of each character in the `newCount`.
- Iterate over the `baselineCount` and `newCount` and update the `baselineCount` with the minimum of both.
- This will give us the count of each character that is common in all the words seen so far.
- Iterate over the `baselineCount` and for each character that has a count greater than `0` add it to the answer.
- Return the answer.

This problem is about finding the common characters in a given set of strings.