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.
-
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. -
For each string in the given list, calculate the frequency count of each character and update the minimum frequency in the
commonCount
array. -
Eventually,
commonCount
will have the minimum count of each character (a-z
) across all strings. -
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.