Leetcode 1002. Find Common Characters

Problem Explanation

In this problem, we are given an array of lowercase strings. Our task is to find all the common characters (including duplicates) that occur in all the strings. We need to return a list of all these characters.

Let's take an example to understand this clearly.

Example

Input: ['bella','label','roller']

In this example, we can see that the characters 'e' and 'l' are common in all the strings. But the character 'e' occurs only once in each string whereas the character 'l' occurs twice in each string. So we need to return the list ['e', 'l', 'l'].

Approach

The approach to the problem is using a frequency counter or a hashmap.

  1. Initialize an array commonCount of size 26 to INT_MAX. This array will keep count of minimum frequency of each character in all the strings.

  2. For each string in the given list, calculate the frequency count of each character and update the minimum frequency in the commonCount array.

  3. Eventually, commonCount will have the minimum count of each character (a-z) across all strings.

  4. Finally, we iterate over commonCount and append each character to the output list as many times as its count.

Solution

Python

1
2python
3class Solution:
4    def commonChars(self, A: List[str]) -> List[str]:
5        # Initialize the commonCount list with max value
6        commonCount = [float('inf')] * 26
7
8        for a in A:
9            # Count the frequency of each character in the string 
10            count = [0] * 26
11            for c in a:
12                count[ord(c) - ord('a')] += 1
13            # Update the minimum count of each character
14            for i in range(26):
15                commonCount[i] = min(commonCount[i], count[i])
16
17        # Return the characters of min frequency
18        return [chr(i + ord('a')) for i in range(26) for _ in range(commonCount[i])]

Java

1
2java
3class Solution {
4    public List<String> commonChars(String[] A) {
5        int[] commonCount = new int[26];
6        Arrays.fill(commonCount, Integer.MAX_VALUE);
7        for (String a : A) {
8            int[] count = new int[26];
9            for (char c : a.toCharArray())
10                count[c - 'a']++;
11            for (int i = 0; i < 26; ++i)
12                commonCount[i] = Math.min(commonCount[i], count[i]);
13        }
14
15        List<String> ans = new ArrayList<>();
16        for (char c = 'a'; c <= 'z'; ++c)
17            for (int i = 0; i < commonCount[c - 'a']; ++i)
18                ans.add("" + c);
19        return ans;
20    }
21}

C++

1
2cpp
3class Solution {
4public:
5    vector<string> commonChars(vector<string>& A) {
6        vector<int> commonCount(26, INT_MAX);
7        
8        for (const string& a : A) {
9            vector<int> count(26);
10            for (char c : a)
11                count[c - 'a']++;
12            
13            for (int i = 0; i < 26; ++i)
14                commonCount[i] = min(commonCount[i], count[i]);
15        }
16        
17        vector<string> ans;
18        for (char c = 'a'; c <= 'z'; ++c)
19            for (int i = 0; i < commonCount[c - 'a']; ++i)
20                ans.push_back(string(1, c));
21        
22        return ans;
23    }
24};

C#

1
2csharp
3public class Solution {
4    public IList<string> CommonChars(string[] A) {
5        int[] commonCount = new int[26];
6        Array.Fill(commonCount, int.MaxValue);
7        
8        foreach (var a in A) {
9            var count = new int[26];
10            foreach (var c in a)
11                count[c - 'a']++;
12            
13            for (int i = 0; i < 26; ++i)
14                commonCount[i] = Math.Min(commonCount[i], count[i]);
15        }
16        
17        List<string> ans = new List<string>();
18        for (char c = 'a'; c <= 'z'; ++c)
19            for (int i = 0; i < commonCount[c - 'a']; ++i)
20                ans.Add(""+c);
21        
22        return ans;
23    }
24}

JavaScript

1
2javascript
3var commonChars = function(A) {
4    let commonCount = new Array(26).fill(Number.MAX_SAFE_INTEGER);
5    
6    for (let a of A) {
7        let count = new Array(26).fill(0);
8        for (let c of a)
9            count[c.charCodeAt(0) - 'a'.charCodeAt(0)]++;
10        
11        for (let i = 0; i < 26; ++i)
12            commonCount[i] = Math.min(commonCount[i], count[i]);
13    }
14    
15    let ans = [];
16    for(let i = 0; i < 26; ++i)
17        for (let j = 0; j < commonCount[i]; ++j)
18            ans.push(String.fromCharCode(i + 'a'.charCodeAt(0)));
19    
20    return ans;
21};

Note: The above solution is in Python, Java, JavaScript, C++, and C#. All of them apply the same algorithm and technique. Depending on the programming language, the syntax might vary.# Conclusion

The goal of the common character finder problem was to determine which letters (if any) appear in a series of words or strings. From our perspective, the solution was quite simple: build a counter for each word, and then compile the minimum count for each letter from across all words.

We used Python, Java, JavaScript, C++, and even C#, demonstrating that this type of problem can be solved efficiently in various programming languages. We utilized traditional for-loops and several comprehensive methods to build our solution.

In conclusion, this problem provides a basic introduction to character counting and string manipulation. It exemplifies how simple data structures like arrays and hashmaps can be efficiently used to solve a problem that might seem confusing at first glance.

Whether learning to code, refining your coding skills, or preparing for an interview, this common character finder problem highlights foundational programming concepts and strategies.

Remember: the more problems you solve, the better you become at identifying patterns and strategies in algorithms. Practice regularly, and continue to challenge yourself!


Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫