Pankaj Tanwar
Published on

Count the Number of Consistent Strings.

––– views

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

Tweet this article