✅ Find Common Characters - LeetCode 1002 - Frequency Array - Strings -Explained in Detail

hello guys and welcome back to lead Logics this is the find common characters problem from lead code and the number for this is 102 so in the given problem we have a string array words and we have to return an array of all the characters that show up in all the strings within the words including duplicates and we can return the answer in any order so let's see first example so the words are Bella label and roller so you can see E L and L so l two times and E one times appear in all the three words in the words areay so therefore we have to return e and l l in the final array so how we are going to do this so for this we are going to use the frequency table to solve the problem and since the problem requires finding common characters that appear in all the strings and we have to include the duplicate as well so therefore we'll be using a frequency counting method so in the approach we are going to uh count the frequency of each the charact each character appearing in the each word and then we are going to take the minimum of all the frequencies in all the words so how we are going to do this so let me explain you using the first example so we have taken this first example Bella label and roller so first of all we are we are going to take create a frequency array for the first word and this will be our reference frequency table for all the other words so first of all find the count of frequency for each character in the word Bella so like we are going to count Bella so a one time B one time e one time and l two times other character Zero so we have created a frequency table for the first word now what we are going to do is that we are going to uh create frequency table of other words and compare it with our reference table and then we have to take the minimum of the current table and the reference table and we have to update it with uh with the new reference table so suppose we have created this for Bella now we are going to create a frequency table for label and then we are going to compare both of these and check whichever frequency is minimum we are going to keep it and update it in a reference table and then the reference table will be used with the other word roller so okay we are going to use so first of all we have created the frequency table for Bella you can see now in the next step we are going to create the frequency table for label now in this case the frequency table or array for the label is exactly same as the frequency table for the Bella so you can see a one time B one time E1 time and l two times which is same as the Bella so in this case there will be no change in the updated uh in the reference table like you can see since both of are equal we we are not going to select minimum because both are same and the updated frequency reference table is still the same but as soon as we U count the frequency table for the roller we are going to get some changes we got one e e one time l two times r one time and r two times another character Z so this this currently is the current frequency table and this was the last reference table so from both of these we have to select the minimum frequency so if we are going to do this like you can see a it was one time and in this it is zero so updated is zero B was one time in the reference zero in the roller so updated is zero e was one in the label one in the roller so updated is one L was two in theb table two in the roller so updated frequency is two so this is uh the final updated frequency reference table what we get we got and uh this will be our answer like E1 times and L2 times so but now we have to create a string from the given frequency array so for that we are going to Simply build a string using this so you can see the summary the initial reference table was this after Bella after label there was no change but after ruler it became like this so let come let's come to the coding section but before that do like the video and share it with your friends and subscribe to the channel so this is the code for this so here we are going to define the frequency reference table so the reference table we were U calculating the reference table for the first word initially and that becomes the reference for the other words so we have created the reference table now we are going to check it for the other words and compare so that's why we have taken I from one till words. length and then we are going to inter do the intersection of the our reference table that is the last along with the new or the current reference current frequency table or that is the count of words of far now this count method what it does is that it simply counts the number of characters appearing number of characters appearing in the word and then create a frequency array and return that frequency array and then we have another function intersection that takes input two arrays A and B and what it does is that it Returns the minimum of a of I and B of I so which means that it Returns the minimum of the frequency of both from a a and b whichever is minimum it returns that so we have come made the reference table we have compared it with all the other words now the last step was to build the array so for building the array we are going to declare a uh list of string this is we are doing because the return type is list of string and then we are going to compare uh not compare we are going to check uh how many frequency do we have in the frequency table and if the frequency is not zero we are going to add the characters the same number of time it appears in the frequency table and for this we are going to use a while loop and decrement the frequency and add it in the string till the time it becomes zero so this is how we are going to solve the question you can check the code here you can see the code here uh you can also check my solution from the lead code solution panel this is my solution you can go into the solutions panel and you can see you can read the intuition the approach step by-step explanation which is I've explained you here the complexity so the time complexity for this is O of n cross M because we are using the we are calculating for n words and for M characters that's why it is n cross n and the space complexity is O of M because we are using a space of charact storing the characters you can also check the Java C++ Python and the JavaScript code in this so I hope you understood the logic do like the video share it with your friends and subscribe to the channel if you're new to the channel thank you for watching the video have a nice day

Channel: Leet Logics

Views: 2,327

Keywords: leetcode, leetcode 1002, 1002, 1002 leetcode, potd, problem of the day, find common characters

Id: gEE5YPQ7pkw

Length: 7min 53sec (473 seconds)

Published: Wed Jun 05 2024