Count the Number of Consistent Strings | Using Bit Manipulation | Leetcode 1684 | codestorywithMIK

This is the 54th Video of our Playlist "Leetcode Easy : Popular Interview Problems" by codestorywithMIK

In this video we will try to solve an easy problem : Count the Number of Consistent Strings | Using Bit Manipulation | Leetcode 1684 | codestorywithMIK

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.
Also, please note that my Github solution link below contains both C++ as well as JAVA code.

Problem Name : Count the Number of Consistent Strings | Using Bit Manipulation | Leetcode 1684 | codestorywithMIK
Company Tags : will update soon

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

Summary :
Approach-1 (Using HashSet)

Time Complexity: O(m + n*k) where m is the length of allowed, n is the number of words, and k is the average length of each word.
Space Complexity: O(m) for storing the allowed characters in an unordered set.
Description: This approach uses a HashSet to store allowed characters. For each word, it checks if all its characters are present in the set. If a character is missing, the word is considered inconsistent. This method is efficient in character lookup due to the O(1) average time complexity of set operations.
Approach-2 (Using Boolean Array)

Time Complexity: O(m + n*k)
Space Complexity: O(m) (actually O(26), which is constant, but generally expressed as O(m) for larger alphabet sizes).
Description: A boolean array of size 26 is used to mark the presence of allowed characters. For each word, we check if all characters are present by referencing the boolean array. If a character is absent, the word is inconsistent. This approach avoids hashing and offers a more memory-efficient solution for a fixed alphabet size.
Approach-3 (Using Bit Manipulation)

Time Complexity: O(m + n*k)
Space Complexity: O(1)
Description: This method uses bit manipulation to create a bitmask representing the allowed characters. Each bit in the mask corresponds to a character from 'a' to 'z'. For each word, the method checks if all characters are allowed by comparing their corresponding bits in the mask. It’s highly space-efficient since the bitmask uses only 32 bits (constant space).
Key Differences:

Space Efficiency: The bit manipulation approach (Approach-3) is the most space-efficient with O(1) space, while the other two require O(m) space.

✨ Timelines✨
00:00 - Introduction

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook #leetcode #computerscience #leetcodesolutions #leetcodequestionandanswers #code #learning #dsalgo #dsa #coding #programming #100daysofcode #developers #techjobs #datastructures #algorithms #webdevelopment #softwareengineering #computerscience #pythoncoding #codinglife #coderlife #javascript #datascience #leetcode #leetcodesolutions #leetcodedailychallenge #codinginterview #interviewprep #technicalinterview #interviewtips #interviewquestions #codingchallenges #interviewready #dsa #hindi #india #hindicoding #hindiprogramming #hindiexplanation #hindidevelopers #hinditech #hindilearning #helpajobseeker #jobseekers #jobsearchtips #careergoals #careerdevelopment #jobhunt #jobinterview #github #designthinking #learningtogether #growthmindset #digitalcontent #techcontent #socialmediagrowth #contentcreation #instagramreels #videomarketing #codestorywithmik #codestorywithmick #codestorywithmikc #codestorywitmik #codestorywthmik #codstorywithmik #codestorywihmik #codestorywithmiik #codeistorywithmik #codestorywithmk #codestorywitmick #codestorymik #codestorwithmik

[how-about-no_]

Hello Sir !! I got placed at McCain as SDE . All credits goes to you, My streak is not as long as you , but close to 200 , Thank you very much, Commenting from a dummy account because sharing this information is not allowed .

[tanujasharma]

learned a new way to solve this question

[shraban]

cooker ki chitti aur sir ki explanation

[DevOpskagyaan]

Every time I come here, i learn something from this legend

[iayushsharma]

Although i solved this question using set and map I thought not to watch today's video but glad I did watch it got to learn that we can also solve this using Bit Manipulation. Thanks, MIK bhaiya you always teach me something

[kaustubhchaudhari]

We can assume Mik is back from 'Hiring drive' when the Cooker's whistle is blowing in the Video, More power to you. :)

[varunpalsingh]

Plz make a video on roadmap to get into high packages, what are the thing to know, like backend, caching, search, frontend

[DevanshGupta-iorl]

vector<int>temp(26, 0);
for(auto c: allowed) temp[c-'a']=1;
int ans=0;
for(auto word: words){
int flag=1;
for(auto c: word){
if(temp[c-'a']==0){
flag=0;
break;
}
}
ans+=flag;
}
return ans;
i used mapping because constraints are small

[saarvikjaiswal]

Hi Mik bhai, I’m requesting you for a favour that is to make a miscellaneous playlist for beginners, like starting from basic topics to intermediate and then advance topic problems in a single playlist doesn’t matter it contains more than 150+ videos or more but It’ll be a one stop playlist for beginners I hope you understand

[crazyaryalucky]

int countConsistentStrings(string allowed, vector<string>& words) {
unordered_set<char> st;

for (auto it : allowed) {
st.insert(it);
}

int n = words.size();
int cnt = 0;
bool check = false;

for (int i = 0; i < n; i++) {
string str = words[i];
for (auto it : str) {
if (!st.count(it)) {
check = true;
}
}
if (!check)
cnt++;

check = false;
}
return cnt;
}

[ArshBakshiVlogs]

bro why didn't you upload a video yesterday ? i had my doubt in yesterdays dailly question and i like ur way of explaining more than anyone's so i was waiting for ur video .

[muntajir]

The set method should be constant space no? As there can be a maximum of 26 size set in worst case.

[bunnypubg]

Hello mik sir, I gave an amazon OA, and one of my solutions didn’t get accepted because of TLE but I still can’t figure out it’s optimal solution, can you help me, where can I send you the picture of the question?

[surendrapokala]

Bhaiya plz expalin this question
leetcode : 798. Smallest Rotation with Highest Score

[GateDA-omkarpunjaji]

class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {

int mask = 0;
for(auto chr : allowed) {
int idx = chr - 'a' ;
mask = (mask | 1<<idx );

}
int res = 0;
for(auto word : words){
int temp = 0;
for(auto &chr : word){
int idx = chr - 'a' ;
temp = temp | (1<<idx);
}
if( mask == (mask | (temp ^ mask))) res++;
}
return res;
}
};

[gyandyan]

int countConsistentStrings(string allowed, vector<string>& words) {
int cnt=0;
int flag=0;
for(auto &wrd:words){
for(auto &ch:wrd){

flag=1;
}
else{
flag=0;
break;
}
}
if(flag==1) cnt++;
}
return cnt;
}

[VanshGupta]

class Solution {
public:
int countConsistentStrings(string allowed, vector<string>& words) {
unordered_set<char>st(allowed.begin(), allowed.end());
int count = 0;
for(auto &x : words){
bool c = 1;
for(auto &i : x){
if(st.find(i) == st.end()){
c = 0;
break;
}
}
if(c) count++;
}
return count;
}
};

[bhaisaheb]

why (mask >> n) & 1 works but mask & (1 << n) doesnt?

[aizadiqbal]

but the SC and TC is same as other approaches, so not much difference right ?

[Kaushikee]

bhaiiya kabhi java me bhi code kiyaa week me teen din java me code kiya kroo, ,