Pankaj Tanwar
Published on

Count the Number of Consistent Strings.

Authors

I could not maintain my streak last weekend. I missed solving problems for day #11 and #12. Well, going forward, I will have to be more serious about it.

Problem of the day - Count the Number of Consistent Strings

Tag - Easy

So, the problem says, you are given a string allowed consisting of distinct characters and an array of strings words. A string is consistent if all characters in the string appear in the string allowed.

Return the number of consistent strings in the array words.

Example 1:

Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
Output: 2
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.


Problem seemed very easy at first glance but it had a really interesting face when I deep dived into the performance analysis of my solution. Stay with me till the end of this solution, you won't regret.

When I looked at the problem, very first approach came to my mind (like any other programmer), maintain a hash map for allowed words. iterate over each word and just check if each character is present in hash map. easy peasy right!

I was excited, directly coded my solution -

class Solution {
public:
bool is_consistant(string word, map<char,int> list) {
for(char c: word) {
if(list[c] == 0) return false;
}
return true;
}
int countConsistentStrings(string allowed, vector<string>& words) {
map<char,int> list;
int res = 0;
for(char c: allowed) list[c]++;
for(auto word: words) {
res += is_consistant(word, list) ? 1 : 0;
}
return res;
}
};

Woohooo! all test cases passed.

WTH. Run time 400ms, memory 161.8MB. faster then 0.1% solutions.

I had the worst submission of my whole life in front of me.

I started figuring out ways to optimize the solution. A random thought came to my mind, bro, don't use a separate function.

I immediately, modify my code (with hope of some better stats).

Modified code -

class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {
map<char,int> list;
int res = words.size();
for(char c: allowed) list[c]++;
for(auto word: words) {
for(char c: word) {
if(list[c] == 0) {
res--;
break;
}
}
}
return res;
}
};

No logic changes, everything almost same. Let's see if some thing changed.

Holy shit, Run time 68ms, memory 30.3MB. I just beat 40% of submissions by just combining logic in one function. Is it for real?

Well, It's still slow. What else I can do here?

Long time back, I learned a trick which says, use an array of length 26 instead of hash map whenever you need to deal with alphabets and their counts.

I decided to try that here. I removed hashmap and used a simple array of length 26.

My code looked like this -

class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {
int list[26] = {};
int res = words.size();
for(char c: allowed) list[c - 'a']++;
for(auto word: words) {
for(char c: word) {
if(list[c - 'a'] == 0) {
res--;
break;
}
}
}
return res;
}
};

That was great. It beat 82% of submissions with run time 52ms and 30mb memory usage. I checked out discuss tab but it seems this is the optimal solution.

My learning from this problem

  • An extra function can slow down (can add extra memory) to your solution
  • Hashmaps are costly. Try array of 26 length if we are dealing with alphabets and their counts

You might like previous editions of my coding diary