Table of Contents
Problem Statement
In this problem, we are given a list of string. We have to find out the characters that are common in all the strings. If a character is present in all strings in multiple times, then we have to output the character multiple times.
Suppose, we have array of strings
[“bella”,”label”,”roller”]
We can see that, character ‘e’ is present once in all strings, l is present twice in all strings. No other character is common.
So, in our output list, character ‘e’ will be present once and character ‘l’ will be present twice.
Example
["bella","label","roller"]
["e","l","l"]
["cool","lock","cook"]
["c","o"]
Approach
We can see that we have to find out the common frequency of characters a-z in all strings here.
For every string we can create a count array of size 26, which is having frequency of characters a-z. index 0 will have count of ‘a’ in that string and index 1 has count of ‘b’ and so on.
Now for each character from a to z, we have to find out the minimum count which may be present in any of the arrays created above. We are doing this, because we are interested in minimum presence of a character in all strings. In other words, we are only taking common characters from each string.
So, we will firstly create an ans array of size 26 which is having all indexes set at max value.
Then, we will traverse the array of strings from left to right. In each step, we will create the count array for current string. Then we will compare the current created array with ans array.
Because we are interested in minimum of all, thus each index of ans array will only be modified if the value in current array is smaller than ans array’s value at that index.
i.e. if ans[i]<arr[i] then ans[i]=arr[i] else no change.
After we have traversed all strings of the given list, we will use our ans array to create the list of characters. In answer array, the value at index 0 shows count of character ‘a’, value at index 1 shows count of index ‘b’ and so on.
So, in this way we will make our output array of characters by using count of each character from a to z.
Implementation
C++ Program for Find Common Characters Leetcode Solution
#include <iostream>
#include <vector>
using namespace std;
vector<string> commonChars(vector<string>& A) {
int ans[26];
int temp[26];
fill(ans,ans+26,100);
for(string str:A){
fill(temp, temp+26,0);
for(int i=0;i<str.size();i++){
temp[str[i]-'a']++;
}
for(int i=0;i<26;i++){
ans[i]=min(ans[i],temp[i]);
}
}
vector<string>ansChars;
for(int i=0;i<26;i++){
for(int j=0;j<ans[i];j++){
char ch=((char)(i+'a'));
string s(1, ch); //convert char ch to string s
ansChars.push_back(s);
}
}
return ansChars;
}
int main()
{
vector<string>A{"bella","label","roller"};
vector<string>ans = commonChars(A);
for(string str:ans){
cout<<str<<" ";
}
cout<<endl;
}
e l l
Java Program for Find Common Characters Leetcode Solution
import java.util.*;
import java.lang.*;
class Solution
{
public static void main(String args[])
{
String[]A={"bella","label","roller"};
List<String>ans=commonChars(A);
for(String str:ans){
System.out.print(str+" ");
}
System.out.println();
}
public static List<String> commonChars(String[] A) {
int[]ans=new int[26];
int[]temp=new int[26];
Arrays.fill(ans,Integer.MAX_VALUE);
for(String str:A){
Arrays.fill(temp,0);
for(int i=0;i<str.length();i++){
temp[str.charAt(i)-'a']++;
}
for(int i=0;i<26;i++){
ans[i]=Math.min(ans[i],temp[i]);
}
}
List<String>ansChars=new ArrayList<String>();
for(int i=0;i<ans.length;i++){
for(int j=0;j<ans[i];j++){
ansChars.add((char)(i+'a')+"");
}
}
return ansChars;
}
}e l l
Complexity Analysis for Find Common Characters Leetcode Solution
Time Complexity
O(n): where n is sum of length of all the strings.
Space Complexity
O(1): two arrays ans and temp, each of size 26 is used. which is nothing but a constant size memory. Thus space complexity is O(1).