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:

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