Awesome explanation. Was able to code easily after watching 30 mins of video. Thanks @Aditya Verma !!!! Java code - public class Anagrams { public static void main(String[] args) { String str = "aabaabbabbabaa"; String ptr = "aaba"; int sum = 0; int count = 0; int k = ptr.length(); Map map = new HashMap(); for(int i=0;i
Gist of the logic: 1. Create an unordered map for the given pattern. The map stores all the distinct characters of the pattern as keys, and their frequencies as values. Create a variable count, which has the count of all the distinct characters in the pattern, which is the size of the map. Create another variable for storing the actual answer. 2. Inside the while loop, compare the jth character with the keys of the map. If this character is found in the map, decrement its corresponding value. If the value of any of the keys becomes 0, decrement the value of count. It means that you’ve found one character in its required quantity in your current window. Like this if for every character in the map, the value becomes 0, then the value of count becomes 0, and it signifies that the current window is an anagram of the pattern. We’re using this count variable to signify whether the window is an anagram or not(in O(1) time), otherwise we have to traverse the whole map for checking if every corresponding value has become 0 or not, and it would have taken O(K) time. 3. When you’ve reached the window size, you need to do 2 things:- a) Retrieving the answer- if the count becomes 0, anagram is found, increment the value of ans variable. b) Sliding the window- before sliding the window, we need to remove all the calculations regarding the first element in the current window. If it exists in the map, then we need to increment the corresponding value in the map. Why we’re incrementing its value because, this character is not going to be there in our next window, so if it has contributed in making an anagram for our previous window, we need to delete its appearance or significance in the map, which tells that there’s a gap which needs to be filled by the next incoming character to complete this incomplete anagram. And only if the corresponding value in the map has become 1, we’ll increment the value of count, and not for any other case. For eg:- Pattern- aaba Current state of Map - a->3 b->1 count=2 window has:- acbe Current state of Map - a->2 b->0 count=1 (what current state of the map signifies is, we need 2 more a's to complete an anagram) We have to remove this 'a', as it is the first element of the current window, because we need to move ahead now:- window is: cbe_ Current state of the map- a->3 b->0 count=1 (this state of the map signifies that we need 3 a's to find an anagram) In such case we’re removing this ‘a’ from the window, so we increment its value to 3, we shouldn’t increment the value of count in this case. Increment the count only if the corresponding value becomes 1 after incrementing it. Because the whole part of ‘a’ is not gone by removing the first element of the previous window, some part of it is gone with it. When the whole part is gone, then we can say that okay, there’s one more character which needs to be found in the next window in its whole quantity.
@@Apex-pn7tr thank you for clarification. i get it. I am learning DSA. would you like to solve together. means we could help each other, occasional doubts etc.
we can also use vector of size 26 instead of using map; int search(string pat, string txt) { int n = txt.length(); // length of txt int k = pat.length(); // window size // variable to store count of the occurences of anagrams of word in the text int ans = 0; // storing frequency of characters in string : pat vectorhashPat(26,0); for(int i = 0;i
Damn, how could we think exactly the same. I also did the same before watching the video. Here is my solution: bool check(int a[], int b[]){ for(int i=0;i
I have also used the same approach used by you (two vectors of size 26), but my code (please read it from below & suggest changes) doesn't run on GFG correctly. The output for the test case is 0. Please help. Has your code run on GFG ? int search(string s, string ptr) { int i = 0, j = 0, k = ptr.length(), count = 0; vector charCount_window(26, 0); vector charCount_ptr(26, 0); // Find frequency of each character in string ptr for (int i = 0; i < k; i++) { charCount_ptr[ptr[i] - 'a']++; } while (j < s.length()) { // Calculations // Find frequency of each element when traversal of j occurs charCount_window[s[j] - 'a']++; int window_size = j - i + 1; if(window_size < k){ j++; } if (window_size == k) { // Devise a way to evaluate answer from calculation if(charCount_ptr == charCount_window){ count++; charCount_window[s[i] - 'a']--; } } i++; j++; } return count; }
@AdityaKumar-ow1rh ig we can also do by storing that substring between the indexes and then compare both the strings by sorting...if equal then well good
As a newbie to DS and algo type questions, I am very thankful for your explanation and way of teaching. The effort you've put into your videos is not short of the effort professors are expected to put in their teaching. There are some places where your explanation could've been better (such as places where you were calling "s" "arr" or when you wrote if count == 1 when you meant something else) but, otherwise, amazing explanation and teaching!
answer for all my Python kings and queens out there def getCountOFAnagram(string,pattern): n=len(string) start=0 end=0 d=dict() ans=0 k=len(pattern) for i in pattern: d[i]=d.get(i,0)+1 count=len(d) while end
Before watching the solution, I tried to solve it on my own. I first tried to store the ASCII sum of the letters in the window. When the window size matches AND the sum of the characters in the window matches the sum of "for", I incremented the count. But now I can see why this method would fail to generalize over all cases. Thanks Aditya Verma!
Thank You So Much for making this series..... I searched alot, so many website, pdfs and youtube video but i could not understand how to approach these "Sliding Window" problems.... I was lookingg for some basic structure kind of thing for sliding window technique..... and you delivered EXACTLY what i was looking for. Once again THANKS A LOT.
#include using namespace std; int countOccurance(string s, string p){ unordered_map mp; int ans = 0; //storing the occ. of string p in the map for (auto &x : p){ mp[x]++; } int count = mp.size(); int k = p.size(); int i=0, j=0; while (j < s.size()){ //calculation part if (mp.find(s[j]) != mp.end()){ mp[s[j]]--; if (mp[s[j]] == 0){ count--; } } //window length not achived yet if (j-i+1 < k){ j++; } //window length achived, find ans and slide the window else if (j-i+1 == k){ //finding the ans if (count == 0){ ans++; } if (mp.find(s[i]) != mp.end()){ mp[s[i]]++; if (mp[s[i]] == 1){ count++; } } //slide the window i++; j++; } } return ans; } int main(){ string s, p; cin >> s; cin >> p; cout
for anyone wondering why we are checking: if (mp[s[i]] == 1){ count++; is becoz in this we will find whether there is transition of any char from 0->1 in that case *only* we need to inc. our count
@@nit_gaal and Shalini... Since we are using a map to mark the frequency of characters so while sliding the window it may be possible that a character's frequency changes from 0 to 1 so in that case we increase the count...
As of now, we are student so we don't have money to pay on pateron but when we will be in good stable condition we will definitely help you on pateron and please make more videos in any topic. its good to see your explanation. 😍😍😍😍
Aditya, create work. I was always avoiding learning this topic but you have explained in simpler way. here is my java solution public static int OccuranceofAnagram(String s, String t){ int result =0; int windowsize = t.length(); int start =0; int end=0; char[] charArray = t.toCharArray(); // Sort the character array Arrays.sort(charArray); // Create a new string from the sorted character array String sortedString = new String(charArray); String createString = ""; while(end < s.length()){ createString = createString + s.charAt(end);
Amazing Explanation brother! Here is the code written in Java -: class Solution { public List findAnagrams(String s, String p) { List ans = new ArrayList();
//Create the HashMap HashMap map = new HashMap();
for(char ch: p.toCharArray()){ if(map.containsKey(ch)){ map.put(ch, map.get(ch) + 1); } else { map.put(ch, 1); } } //Number of Distinct letters the pattern have int count = map.size(); //Size of the window int k = p.length(); int i = 0; int j = 0; while(j < s.length()){ char ch = s.charAt(j); if(map.containsKey(ch)){ map.put(ch, map.get(ch) - 1); if(map.get(ch) == 0){ count--; } } if(j - i + 1 < k){ j++; } else{ if(count == 0){ ans.add(i); } //Slide the window char ch1 = s.charAt(i); if(map.containsKey(ch1)){ map.put(ch1, map.get(ch1) + 1); if(map.get(ch1) == 1){ count++; } } i++; j++; } } return ans; } }
I thought of another approach. We create a duplicate of mp as mp2(to make changes in while checking ) where we just make i=j+1 and then j++ whenever mp2[s[j]] ==0 while decrementing the count of letters present in s and in pattern and then continue the same process. Once we reach the end of the window, we are sure that all the chars are present in the pattern and increment answer by one and because mp2 might be altered, we set mp2=mp and repeat until end os string.
In Javascript, we can do following var findAnagrams = function (s, p) { // initialize output array to be returned at the end and neededChars object to store the chars in p. const output = []; const neededChars = {}; // populate neededChars to contain every char in p as a key and how many times that char appears in p as its value. for (let char of p) neededChars[char] = (neededChars[char] || 0) + 1; // initialize window pointers and the total number of chars needed to form an anagram. let windowStart = 0; let windowEnd = 0; let count = p.length; // start sliding the window while (windowEnd < s.length) { // if the current char is found in p and is currently needed (meaning that its value in neededChars is bigger than 0), // then decrease the count which is the total number of chars that are needed and that still haven't been found. if (neededChars[s[windowEnd]] > 0) { count--; } // decrease the needed amount for the current char and move the window's right end one step forward. s[windowEnd] in neededChars && neededChars[s[windowEnd]]--; // at first, the window will increase its length by taking steps forward with its right end. // after the window length reaches p's length for the first time, // the window will start moving forward like a caterpillar with the left end moving first. if (windowEnd - windowStart + 1 === p.length) { // if the count is 0, this means that there is an anagram starting at the left index so push left into the output array. if (count === 0) output.push(windowStart); // if the char we need to remove from left is a needed char, increase the total number of chars currently needed to form an anagram. if (neededChars[s[windowStart]] >= 0) count++; // the lines below are the most important to understand: // every time a needed char is left behind (outside the window) as the window moves forward to search the rest of the string, // increment that char's value in the neededChars object (restore the need for that char for the window's future reference). s[windowStart] in neededChars && neededChars[s[windowStart]]++; windowStart++; } windowEnd++; } return output; };
I did another similar approach in which I just used another map for the window and after reaching the window size, checked if both the maps are equal or not, without using the count variable thing. Memory used is more, but it was the first approach that occurred to me without watching the video. Code : int search(string pat, string txt) { // code here unordered_map mp; unordered_map mpp; int n = txt.size(); int k = pat.size(); int ans = 0; for(auto &x:pat) { mp[x]++; } int i=0, j=0; while(j < n) { mpp[txt[j]]++; if(j-i+1 < k) { j++; } else if(j-i+1 == k) { if(mp == mpp) { ans++; } mpp[txt[i]]--; if(mpp[txt[i]] == 0) { mpp.erase(txt[i]); } i++; j++; } } return ans; }
great video bhaiya...main aapka solution dekhne se pehele he solution banaliya tha bcuz of ur previous videos that i had watched as my concepts were crystal clear by watching ur videos. Step1 : find all the permutation in the string 2 i.e "for" and store it in set st; step2 : now use sliding window concept and check whether that k window size string is in set or not; if that k size window string is in set then : count++; move the window and iterate the whole string 1; Bhaiya is this concept correct?
bro for finding all anagrams u have to use recursion and backtracking which has polynomial time complexity.... then what ;s the use of sliding window , do directly in O(n^2) , by using two for loops
in case within the window there is a character which is not present in the pattern string (eg. 28:09), then instead of sliding the window by 1 position, could we not directly slide it till we move out of that unwanted character ('c' in that example)
Solution in C++ code for above problem with slight change in output, here we have to return starting index of each anagram instead of total count: class Solution { public: vector findAnagrams(string s, string p) { int n = s.size(); map mp; int k = p.size(); for(int i = 0; i < k; i++){ mp[p[i]]++; } int count = mp.size(); int i = 0; int j = 0; vector v; while(j < n){ if(mp.count(s[j]) == 1){ mp[s[j]]--; if(mp[s[j]] == 0){ count--; } } int l = (j - i + 1); if(l < k){ j++; } else if(l == k){ if(count == 0){ v.push_back(i); } if(mp.count(s[i]) == 1){ mp[s[i]]++; if(mp[s[i]] == 1){ count++; } } i++; j++; } } return v; } };
If anyone is having problem implementing this approach or if all test cases are not passing in gfg then try this: int search(string pat, string txt) { vector ans(26,0); vector arr(26,0); for(int i=0;i
For people looking for code, here's my java implementation(Similar question on leetcode q-438 class Solution { public List findAnagrams(String s, String p) { List ans = new ArrayList(); HashMap m = new HashMap();
//put all elements of pttrn p in map for(int i=0;i
Code of this problem :) int k = pat.length(); int n = txt.size();
// counting pattern char unordered_map mpat; for (int i = 0; i < k; i++) { mpat[pat[i]]++; } // storing unique element size in count int cnt = mpat.size();
// ans store occurence of anagrams i and j is initialization val int ans = 0, i = 0, j = 0; while (j < n) { // calculation // searching pattern in txt if (mpat.find(txt[j]) != mpat.end()) { // if found dec the occ mpat[txt[j]]--; // if occ is 0 in map then dec. cnt of unique ele if (mpat[txt[j]] == 0) { cnt--; } }
// Window Expansion if (j - i + 1 < k) { j++; } else if (j - i + 1 == k) { // pattern match found if (cnt == 0) { ans++; } //remove prev calc if (mpat.find(txt[i]) != mpat.end()) { mpat[txt[i]]++; if (mpat[txt[i]] == 1) { cnt++; } } i++; j++; } } return ans;
//if you're doing this question on gfg just reverse the input parameters of the function int search(string pat, string txt) { unordered_map mp; int anaCount=0; for(int i=0;i
Here is the code for this in java. I've added comments in the code so that it will be useful import java.util.HashMap; class Count_All_Occurrence_Of_Anagram {
public static int countAnagram( String a, String b) { // Putting string b in HashMap (b is the small string or pattern) HashMap hmB = new HashMap(); for(int i=0; i
the explanation was fantastic , but there issue that you didn't discussed the case when a particular window contains a pattern char for example: str = fffor pat: for this was the case which tricked a little :) but rest the explanation was amazing.....
for those who don't get why m[s[i]]==1 then we will do cnt++ because only if m[s[i]] was equal to 0 then only we did cnt-- otherwise cnt remained the same so if m[s[i]]==1 then only we can do cnt++ as earlier we subtracted cnt for it now as the character in no more in our window so m[s[i]]++ and only if m[s[i]]=1 then we increment cnt .
But what is need of that, actually we already check m[s[i]]==0,they we will get our ans na,wht is the need of that last part ,why they again considered a=0,b=0??count =0 can u explain 🥺
// Online C++ compiler to run C++ program online #include #include using namespace std; int main() { string str="aabaabaa"; string str2="aaba"; int N=str.size(); int k=str2.size(); int res=0, count=0; for(int y=0;y
class Solution{ public: int search(string pat, string txt) { unordered_map mp; int ans =0; for(char i : pat) { if(mp[i]>=1) mp[i]++; else mp[i]=1; } int cnt = mp.size(); int i =0; int j =0; int k = pat.size(); while(j
Python Solution with the same logic : Leet code problem : 438. Find All Anagrams in a String from collections import defaultdict from typing import List class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: ans = []
k = len(p) map = defaultdict(int)
for ch in p: map[ch] += 1
count = len(map) i = 0 j = 0
while j < len(s): # Calculation: ch = s[j] if ch in map: map[ch] -= 1 if map[ch] == 0: count -= 1
if j - i + 1 < k: j += 1 elif j - i + 1 == k: if count == 0: ans.append(i) ch1 = s[i] if ch1 in map: map[ch1] += 1 if map[ch1] == 1: count += 1 i += 1 j += 1
Can we not use two separate unordered maps to solve this? One for the pattern to be found, the other to store the characters in the current window? We can then simply compare if (patternMap == temporaryMap) and increase the anagram_count accordingly. Kindly tell me why a single-map approach is preferred? Is it too taxing in terms of space complexity?
O(N) Time complexity code class Solution{ public: int search(string pat, string txt) { // code here int n = pat.size(); int m = txt.size(); if (m < n) { return 0; } unordered_map m1; int cnt = 0; // Initialize the map for the pattern for (char i : pat) { m1[i]++; } // Initialize the map for the first window in the text unordered_map m2; for (int i = 0; i < n; i++) { m2[txt[i]]++; } // Check the first window if (m1 == m2) { cnt++; } // Process the remaining windows for (int j = n; j < m; j++) { // Increment the count for the current character in the window m2[txt[j]]++; // Decrement the count for the character at the beginning of the window m2[txt[j - n]]--; // Remove the character if its count becomes zero if (m2[txt[j - n]] == 0) { m2.erase(txt[j - n]); } // Check if the current window is an anagram of the pattern if (m1 == m2) { cnt++; } } return cnt; } }; 🙅🙅🙅
Great Explaination, problem was bit standard i think brute force would work: as O( (s-p+1)* 26log26 (comparing 2 maps ) ) for each substring of size P in S : we will keep track of chars count using map then when substring size == P compare 2 maps
we can calculate the sum of ascii values of the given string and then we can compare that sum with every sliding window and update the counter.. #include using namespace std; int main(){ string s; getline(cin,s); int n=s.size(); string f; getline(cin,f); int count=0; for(int i=0;i
Na.. this logic is not true always bro.. Input: text = "zbcoejuvpvaboyg " pattern = "po" Its Correct output is: 0 And Your Code's output is: 1 Here ASCII value sum of "po" is 112+111 = 223 and ASCII value sum of "ju" is 106+117 = 223 too 😬, and these r not anagrams
Thank you for this video. Anyone looking for the code. I have implemented it for a similar problem. LC #438 class Solution(object): def findAnagrams(self, s, p): """ :type s: str :type p: str :rtype: List[int] """
# make a dict of count of letters count_letters = {}
for letter in p: if letter not in count_letters: count_letters[letter] = 0 count_letters[letter] += 1
total_count = len(count_letters)
k = len(p)
i, j = 0, 0
answer = []
# print(count_letters, total_count)
while j < len(s):
# for j elements # keep decrementing the count from the dict # and if it reaches 0, we decrement count by 1
if s[j] in count_letters: count_letters[s[j]] -= 1 if count_letters[s[j]] == 0: total_count -= 1
# check if window size is reached
if j - i + 1 < k: j += 1
elif j - i + 1 == k: # we have hit the window
# check if count of distinct characters is zero # if yes, it is an anagram
if total_count == 0: answer.append(i)
# reverse the calculations done at j so far # increment the character count
if s[i] in count_letters: count_letters[s[i]] += 1 if count_letters[s[i]] == 1: total_count += 1
I think you miss one case like when string is abc and bigger string is aaaaaab so when it will calculate count of a it will be negative and will not produce the right output
Even if it became negative suppose ptr= aaba i.e.size 4 so for first window our map[a] = -1 as our first window is aaaa but when we will do i++ 4 times then our map[a] becomes 4 again
Bhaiya what a explanation 👏 👌, mza aa gya yrr, aap jb sumup krne ho na bohot smooth ho jata h sara concepts 💥💯💯 Please bring Playlist for graph and tree Please 🥺🥺
I really appreciate the work you are doing but not coding in editor has it's own disadvantage. One of them is your algos , a few times, give wrong answers and we have to tweak them a lot to get all test cases, which is not good for beginners as it may consume a lot of time. Anyway, it's a great playlist and explanation is really top level.
@@archikashukla7997 !=m.end()) ye kyu kr rhe h ye smjh ni a rha h can u explain me hmm s[i] sirf isse bhi to hm map me check kr skte h na like mp[s[i]] == s[j]
@@archikashukla7997 it's because if s[i] is already in map then we don't need to increase the count, but if s[i] was not present in map (i,e mp[s[i]] == 0 ) then on doing mp[s[i]] ++ we will get mp[s[i]] ==1 , that means a new letter has been mapped so we need to increase the count by 1
Please do permutation in string as well on leetcode to get good hands on variation, and suggest if similar problems are there to work with variation in this type of questions.......
class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: k = len(p) hashMap = {} for char in p: if char in hashMap: hashMap[char] += 1 else: hashMap[char] = 1 count = len(hashMap) i, j = 0, 0 ans = [] while j < len(s): # Calculation if s[j] in hashMap: hashMap[s[j]] -= 1 if s[j] in hashMap and hashMap[s[j]] == 0: count -= 1 # When window is smaller if j - i + 1 < k: j += 1 # When window size is equal elif j - i + 1 == k: # get the answer if count == 0: ans.append(i) # revert the operation for the first element of the window to remove it from the answer # before sliding the window if s[i] in hashMap: hashMap[s[i]] += 1 if hashMap[s[i]] == 1: count += 1 i += 1 j += 1 return ans
you have explained about, increasing count++, if removing element (arr[i++]) present in hashmap while sliding, but what about the new element which will added to the window ? suppose, Str = "foroffroofr"; and ptr = "for"; 1). first window "for", all count in map will be zero and count variable also will be zero. 2). second window we are removing 'f' and adding 'o' then window becomes "oro". In above case count of 'f' in hashmap will become 1, and count variable also becomes 1, but what should be done for adding element 'o' ? because 'o' count in hashmap is already zero so if we decrease it it will become -1. 3) third window "rof", this is creating problem for me. so can you please iterate over this and explain ?
Those who are wondering for the c++ code here it is exact code.... void solve() { int n; cin >> n; string s, t; cin >> s >> t; mapmp; int ans = 0; for (auto c : t)mp[c]++; int i = 0, j = 0, count = mp.size(); while (j < n) { if (mp.find(s[j]) != mp.end()) { mp[s[j]]--; if (!mp[s[j]])count--; } if (j - i + 1 < sz(t)) { j++; } else if (j - i + 1 == sz(t)) { if (!count) { ans++; } if (mp.find(s[i]) != mp.end()) { mp[s[i]]++; if (mp[s[i]] == 1)count++; } i++; j++; } } cout
#include using namespace std; int main() { string s, t; cin >> s >> t; int k = t.size(); map mpp, mpp1; // Populate frequency map for string t for (char ch : t) { mpp[ch]++; } int i = 0, c = 0; int j = 0; while (j < s.size()) { mpp1[s[j]]++; // Add current character to mpp1 // Check if we have a window of size k if (j - i + 1 == k) { // Compare frequencies of characters bool match = true; for (auto& entry : mpp) { if (mpp1[entry.first] != entry.second) { match = false; break; } } if (match) { c++; } // Slide the window mpp1[s[i]]--; // Remove character going out of window i++; } j++; } cout
Great Explaination vro! I found the code in discussion forums but did not get the explaination specially why left pointer moving forward (should decrease the map ) but is increasing. But finaaly i have my fog cleared up!
Python code for Count Occurences from collections import Counter class Solution: def search(self, pat, txt): # Initializing pointers and variables i = 0 j = 0 n = len(txt) k = len(pat) ans = 0
# Create a hashmap with the frequency of characters in the pattern hash_map = Counter(pat) count = len(hash_map)
# Sliding window while i < n: if txt[i] in hash_map: hash_map[txt[i]] -= 1 if hash_map[txt[i]] == 0: count -= 1
if i - j + 1 < k: i += 1 elif i - j + 1 == k: if count == 0: ans += 1 if txt[j] in hash_map: if hash_map[txt[j]] == 0: count += 1 hash_map[txt[j]] += 1 j += 1 i += 1
int search(string pat, string txt) { int i = 0, j = 0; int k = pat.length(); int patSum = 0; // Sum of ASCII values of characters in the pattern int currSum = 0; // Sum of ASCII values of characters in the current window // Calculate the sum of ASCII values of characters in the pattern for (int i = 0; i < k; i++) { patSum += pat[i]; } int ans = 0; // Counter for occurrences while (j < txt.size()) { currSum += txt[j]; if (j - i + 1 < k) { j++; } else if (j - i + 1 == k) { if (currSum == patSum) { ans++; } currSum -= txt[i]; i++; j++; } } return ans; } why this fail, can anyone explain if i use this method instead of map
10 mins into the video and Coded the solution on my own! That's how well he teaches, RESPECT++
same🙌
same for me
Us bro
you must have not understood the question well enough
@@nimeshpareek953 😂😂😂
Awesome explanation. Was able to code easily after watching 30 mins of video. Thanks @Aditya Verma !!!!
Java code -
public class Anagrams {
public static void main(String[] args) {
String str = "aabaabbabbabaa";
String ptr = "aaba";
int sum = 0;
int count = 0;
int k = ptr.length();
Map map = new HashMap();
for(int i=0;i
Thankyou bro 👍
Dude you are the best !! Please complete this series asap .Eagerly waiting for backtracking and graph
LeetCode: 438. Find All Anagrams in a String
Java code:
public List findAnagrams(String s, String p) {
List ans = new ArrayList();
int k = p.length();
HashMap map = new HashMap();
for(int i=0;i
Thank you so much for listing the leetcode problem and solution.
What is the value of any key becomes -1?
Should the count still be 0
could you explain me code from if(j-i+1)
Ans
@@Flux-wc5ns its for checking if the window size has not hit
Gist of the logic:
1. Create an unordered map for the given pattern. The map stores all the distinct characters of the pattern as keys, and their frequencies as values. Create a variable count, which has the count of all the distinct characters in the pattern, which is the size of the map. Create another variable for storing the actual answer.
2. Inside the while loop, compare the jth character with the keys of the map. If this character is found in the map, decrement its corresponding value. If the value of any of the keys becomes 0, decrement the value of count. It means that you’ve found one character in its required quantity in your current window. Like this if for every character in the map, the value becomes 0, then the value of count becomes 0, and it signifies that the current window is an anagram of the pattern. We’re using this count variable to signify whether the window is an anagram or not(in O(1) time), otherwise we have to traverse the whole map for checking if every corresponding value has become 0 or not, and it would have taken O(K) time.
3. When you’ve reached the window size, you need to do 2 things:-
a) Retrieving the answer- if the count becomes 0, anagram is found, increment the value of ans variable.
b) Sliding the window- before sliding the window, we need to remove all the calculations regarding the first element in the current window. If it exists in the map, then we need to increment the corresponding value in the map. Why we’re incrementing its value because, this character is not going to be there in our next window, so if it has contributed in making an anagram for our previous window, we need to delete its appearance or significance in the map, which tells that there’s a gap which needs to be filled by the next incoming character to complete this incomplete anagram. And only if the corresponding value in the map has become 1, we’ll increment the value of count, and not for any other case.
For eg:-
Pattern- aaba
Current state of Map - a->3
b->1
count=2
window has:- acbe
Current state of Map - a->2
b->0
count=1 (what current state of the map signifies is, we need 2 more a's to complete an anagram)
We have to remove this 'a', as it is the first element of the current window, because we need to move ahead now:-
window is: cbe_
Current state of the map- a->3
b->0
count=1 (this state of the map signifies that we need 3 a's to find an anagram)
In such case we’re removing this ‘a’ from the window, so we increment its value to 3, we shouldn’t increment the value of count in this case. Increment the count only if the corresponding value becomes 1 after incrementing it. Because the whole part of ‘a’ is not gone by removing the first element of the previous window, some part of it is gone with it. When the whole part is gone, then we can say that okay, there’s one more character which needs to be found in the next window in its whole quantity.
can we use ASCII value to check if we got our pattern or not. ASCII value of 'aaab'. i.e. 3 * a + 1 * b
@@shaileshkaiwart7190 no it wouldn't work since we could end up at similar sum for different characters , if we go by this approach
@@Apex-pn7tr thank you for clarification. i get it.
I am learning DSA. would you like to solve together. means we could help each other, occasional doubts etc.
Great Explanation
@@shaileshkaiwart7190 i too preparing for the same man
The question came in a Codechef contest yesterday, couldn't think of this approach. The video helps a lot in up-solving thanks :)
Undoubtedly the best ever to teach DSA on youtube.
we can also use vector of size 26 instead of using map;
int search(string pat, string txt) {
int n = txt.length(); // length of txt
int k = pat.length(); // window size
// variable to store count of the occurences of anagrams of word in the text
int ans = 0;
// storing frequency of characters in string : pat
vectorhashPat(26,0);
for(int i = 0;i
❤❤❤nicely written
Damn, how could we think exactly the same. I also did the same before watching the video. Here is my solution:
bool check(int a[], int b[]){
for(int i=0;i
I have also used the same approach used by you (two vectors of size 26), but my code (please read it from below & suggest changes) doesn't run on GFG correctly. The output for the test case is 0. Please help. Has your code run on GFG ?
int search(string s, string ptr) {
int i = 0, j = 0, k = ptr.length(), count = 0;
vector charCount_window(26, 0);
vector charCount_ptr(26, 0);
// Find frequency of each character in string ptr
for (int i = 0; i < k; i++)
{
charCount_ptr[ptr[i] - 'a']++;
}
while (j < s.length())
{
// Calculations
// Find frequency of each element when traversal of j occurs
charCount_window[s[j] - 'a']++;
int window_size = j - i + 1;
if(window_size < k){
j++;
}
if (window_size == k)
{
// Devise a way to evaluate answer from calculation
if(charCount_ptr == charCount_window){
count++;
charCount_window[s[i] - 'a']--;
}
}
i++;
j++;
}
return count;
}
@AdityaKumar-ow1rh ig we can also do by storing that substring between the indexes and then compare both the strings by sorting...if equal then well good
As a newbie to DS and algo type questions, I am very thankful for your explanation and way of teaching. The effort you've put into your videos is not short of the effort professors are expected to put in their teaching. There are some places where your explanation could've been better (such as places where you were calling "s" "arr" or when you wrote if count == 1 when you meant something else) but, otherwise, amazing explanation and teaching!
Ahmed sala
answer for all my Python kings and queens out there
def getCountOFAnagram(string,pattern):
n=len(string)
start=0
end=0
d=dict()
ans=0
k=len(pattern)
for i in pattern:
d[i]=d.get(i,0)+1
count=len(d)
while end
Before watching the solution, I tried to solve it on my own. I first tried to store the ASCII sum of the letters in the window. When the window size matches AND the sum of the characters in the window matches the sum of "for", I incremented the count. But now I can see why this method would fail to generalize over all cases. Thanks Aditya Verma!
i did the same
Do different pair of letters can have same ASCII sums.
Bro.. very good explanation
Aditya verma Sir. U r saviour❤️❤️. Sir aapko hi follow kr rha hu. Backtracking ka wait kr rha hu . Please next Playlist backtracking pr🙏🙏.
Hii can u plz tell me how can I get working code of the video ..or if u have wud u plz share it here
Thank You So Much for making this series..... I searched alot, so many website, pdfs and youtube video but i could not understand how to approach these "Sliding Window" problems....
I was lookingg for some basic structure kind of thing for sliding window technique..... and you delivered EXACTLY what i was looking for. Once again THANKS A LOT.
#include
using namespace std;
int countOccurance(string s, string p){
unordered_map mp;
int ans = 0;
//storing the occ. of string p in the map
for (auto &x : p){
mp[x]++;
}
int count = mp.size();
int k = p.size();
int i=0, j=0;
while (j < s.size()){
//calculation part
if (mp.find(s[j]) != mp.end()){
mp[s[j]]--;
if (mp[s[j]] == 0){
count--;
}
}
//window length not achived yet
if (j-i+1 < k){
j++;
}
//window length achived, find ans and slide the window
else if (j-i+1 == k){
//finding the ans
if (count == 0){
ans++;
}
if (mp.find(s[i]) != mp.end()){
mp[s[i]]++;
if (mp[s[i]] == 1){
count++;
}
}
//slide the window
i++;
j++;
}
}
return ans;
}
int main(){
string s, p;
cin >> s;
cin >> p;
cout
for anyone wondering why we are checking:
if (mp[s[i]] == 1){
count++;
is becoz in this we will find whether there is transition of any char from 0->1 in that case *only* we need to inc. our count
Thanks!~
@@akashsaraf7595 can u explain a bit more i don't get this part
@@akashsaraf7595 pls explain the pt a bit clear
@@nit_gaal and Shalini... Since we are using a map to mark the frequency of characters so while sliding the window it may be possible that a character's frequency changes from 0 to 1 so in that case we increase the count...
Can you please upload a video giving a rough timeline of the topics that you are planning on covering? It will be really helpful. Thanks!
As of now, we are student so we don't have money to pay on pateron but when we will be in good stable condition we will definitely help you on pateron and please make more videos in any topic. its good to see your explanation. 😍😍😍😍
Aditya, create work. I was always avoiding learning this topic but you have explained in simpler way. here is my java solution
public static int OccuranceofAnagram(String s, String t){
int result =0;
int windowsize = t.length();
int start =0;
int end=0;
char[] charArray = t.toCharArray();
// Sort the character array
Arrays.sort(charArray);
// Create a new string from the sorted character array
String sortedString = new String(charArray);
String createString = "";
while(end < s.length()){
createString = createString + s.charAt(end);
if(end-start+1
Amazing Explanation brother!
Here is the code written in Java -:
class Solution {
public List findAnagrams(String s, String p) {
List ans = new ArrayList();
//Create the HashMap
HashMap map = new HashMap();
for(char ch: p.toCharArray()){
if(map.containsKey(ch)){
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
}
//Number of Distinct letters the pattern have
int count = map.size();
//Size of the window
int k = p.length();
int i = 0;
int j = 0;
while(j < s.length()){
char ch = s.charAt(j);
if(map.containsKey(ch)){
map.put(ch, map.get(ch) - 1);
if(map.get(ch) == 0){
count--;
}
}
if(j - i + 1 < k){
j++;
} else{
if(count == 0){
ans.add(i);
}
//Slide the window
char ch1 = s.charAt(i);
if(map.containsKey(ch1)){
map.put(ch1, map.get(ch1) + 1);
if(map.get(ch1) == 1){
count++;
}
}
i++;
j++;
}
}
return ans;
}
}
I thought of another approach. We create a duplicate of mp as mp2(to make changes in while checking ) where we just make i=j+1 and then j++ whenever mp2[s[j]] ==0 while decrementing the count of letters present in s and in pattern and then continue the same process. Once we reach the end of the window, we are sure that all the chars are present in the pattern and increment answer by one and because mp2 might be altered, we set mp2=mp and repeat until end os string.
gay approach hai ye
Hats off guru.... Apke concept faad hai... Bahot saare question solve ho rahe hai ab... Bahot Bahot dhanyabaad
In Javascript, we can do following
var findAnagrams = function (s, p) {
// initialize output array to be returned at the end and neededChars object to store the chars in p.
const output = [];
const neededChars = {};
// populate neededChars to contain every char in p as a key and how many times that char appears in p as its value.
for (let char of p) neededChars[char] = (neededChars[char] || 0) + 1;
// initialize window pointers and the total number of chars needed to form an anagram.
let windowStart = 0;
let windowEnd = 0;
let count = p.length;
// start sliding the window
while (windowEnd < s.length) {
// if the current char is found in p and is currently needed (meaning that its value in neededChars is bigger than 0),
// then decrease the count which is the total number of chars that are needed and that still haven't been found.
if (neededChars[s[windowEnd]] > 0) {
count--;
}
// decrease the needed amount for the current char and move the window's right end one step forward.
s[windowEnd] in neededChars && neededChars[s[windowEnd]]--;
// at first, the window will increase its length by taking steps forward with its right end.
// after the window length reaches p's length for the first time,
// the window will start moving forward like a caterpillar with the left end moving first.
if (windowEnd - windowStart + 1 === p.length) {
// if the count is 0, this means that there is an anagram starting at the left index so push left into the output array.
if (count === 0) output.push(windowStart);
// if the char we need to remove from left is a needed char, increase the total number of chars currently needed to form an anagram.
if (neededChars[s[windowStart]] >= 0) count++;
// the lines below are the most important to understand:
// every time a needed char is left behind (outside the window) as the window moves forward to search the rest of the string,
// increment that char's value in the neededChars object (restore the need for that char for the window's future reference).
s[windowStart] in neededChars && neededChars[s[windowStart]]++;
windowStart++;
}
windowEnd++;
}
return output;
};
I did another similar approach in which I just used another map for the window and after reaching the window size, checked if both the maps are equal or not, without using the count variable thing. Memory used is more, but it was the first approach that occurred to me without watching the video.
Code :
int search(string pat, string txt) {
// code here
unordered_map mp;
unordered_map mpp;
int n = txt.size();
int k = pat.size();
int ans = 0;
for(auto &x:pat) {
mp[x]++;
}
int i=0, j=0;
while(j < n) {
mpp[txt[j]]++;
if(j-i+1 < k) {
j++;
}
else if(j-i+1 == k) {
if(mp == mpp) {
ans++;
}
mpp[txt[i]]--;
if(mpp[txt[i]] == 0) {
mpp.erase(txt[i]);
}
i++;
j++;
}
}
return ans;
}
#include
using namespace std;
int main() {
string s = "forxxorfxaofr";
string f = "for";
int i = 0, j = 0, c = 0;
map m, r;
while (j < f.size()-1) {
r[f[j]]++;
j++;
}
j = 0;
while (j < s.size()) {
m[s[j]]++;
if (j - i + 1 < f.size()) {
j++;
}
if (j - i + 1 == f.size()) {
if (m == r) {
c++;
}
m[s[i]]--;
if (m[s[i]] == 0) {
m.erase(s[i]);
}
i++;
j++;
}
}
cout
Aditya: Video faltu mai lamba ho jata h
Also Aditya : video length 40 Min
love your work man!!!
blessed to have found your channel
This guy is a genius
Please do complete this series!Keep up the good work👍
great video bhaiya...main aapka solution dekhne se pehele he solution banaliya tha bcuz of ur previous videos that i had watched as my concepts were crystal clear by watching ur videos.
Step1 : find all the permutation in the string 2 i.e "for" and store it in set st;
step2 : now use sliding window concept and check whether that k window size string is in set or not;
if that k size window string is in set then : count++;
move the window and iterate the whole string 1;
Bhaiya is this concept correct?
bro for finding all anagrams u have to use recursion and backtracking which has polynomial time complexity.... then what ;s the use of sliding window , do directly in O(n^2) , by using two for loops
in case within the window there is a character which is not present in the pattern string (eg. 28:09), then instead of sliding the window by 1 position, could we not directly slide it till we move out of that unwanted character ('c' in that example)
yes we can
@@shivamgarg8398 how?
@@katana5356 ab toh m bhul gya XD
@@shivamgarg8398 lol
Boyer moore algorithm bad character table
Nice explanation man, could solve by myself, halfway through the video.
bahut badhiya yaar badi mehnat ka kaam hai. Thank you.
Great explanation Sir. LC 438 is a similar question which I could solve easily by your approach in above question.
Thank you bhaiya. Concept puri tarah se chamak gya.
Solution in C++ code for above problem with slight change in output, here we have to return starting index of each anagram instead of total count:
class Solution {
public:
vector findAnagrams(string s, string p) {
int n = s.size();
map mp;
int k = p.size();
for(int i = 0; i < k; i++){
mp[p[i]]++;
}
int count = mp.size();
int i = 0;
int j = 0;
vector v;
while(j < n){
if(mp.count(s[j]) == 1){
mp[s[j]]--;
if(mp[s[j]] == 0){
count--;
}
}
int l = (j - i + 1);
if(l < k){
j++;
}
else if(l == k){
if(count == 0){
v.push_back(i);
}
if(mp.count(s[i]) == 1){
mp[s[i]]++;
if(mp[s[i]] == 1){
count++;
}
}
i++;
j++;
}
}
return v;
}
};
thanks bro
dude!! your explanation is amazing...
Love your recursion and dp playlist brother
👌
If anyone is having problem implementing this approach or if all test cases are not passing in gfg then try this:
int search(string pat, string txt) {
vector ans(26,0);
vector arr(26,0);
for(int i=0;i
bhi ya ans[pat[i]-'a']++ iska mtab
For people looking for code, here's my java implementation(Similar question on leetcode q-438
class Solution {
public List findAnagrams(String s, String p) {
List ans = new ArrayList();
HashMap m = new HashMap();
//put all elements of pttrn p in map
for(int i=0;i
Hi…pls explain the usage of count variable
@@imtech55 count represents the number of entries in a hashmap
Thank you very much. You are a genius.
Code of this problem :)
int k = pat.length();
int n = txt.size();
// counting pattern char
unordered_map mpat;
for (int i = 0; i < k; i++) {
mpat[pat[i]]++;
}
// storing unique element size in count
int cnt = mpat.size();
// ans store occurence of anagrams i and j is initialization val
int ans = 0, i = 0, j = 0;
while (j < n) {
// calculation
// searching pattern in txt
if (mpat.find(txt[j]) != mpat.end()) {
// if found dec the occ
mpat[txt[j]]--;
// if occ is 0 in map then dec. cnt of unique ele
if (mpat[txt[j]] == 0) {
cnt--;
}
}
// Window Expansion
if (j - i + 1 < k) {
j++;
}
else if (j - i + 1 == k) {
// pattern match found
if (cnt == 0) {
ans++;
}
//remove prev calc
if (mpat.find(txt[i]) != mpat.end()) {
mpat[txt[i]]++;
if (mpat[txt[i]] == 1) {
cnt++;
}
}
i++;
j++;
}
}
return ans;
thankyou
Thank You bhaiya
maza a gaya maza a gaya bhaiya.
upar jo ho raha thik uska ulta niche ho raha.
thanks you are finally back!!😊
thank u so much for uploading such an awsm content ....seems like i really found a gem
It was awesome! Its always fun to watch your videos
//if you're doing this question on gfg just reverse the input parameters of the function
int search(string pat, string txt) {
unordered_map mp;
int anaCount=0;
for(int i=0;i
Is this code perfectly working ?
Not properly working on 50 no test case got stuck
What a brilliant man🎉
i love the way you teach
Here is the code for this in java. I've added comments in the code so that it will be useful
import java.util.HashMap;
class Count_All_Occurrence_Of_Anagram {
public static int countAnagram( String a, String b) {
// Putting string b in HashMap (b is the small string or pattern)
HashMap hmB = new HashMap();
for(int i=0; i
mindblowing explanation 💥
what is the name of this application on which you are writing?
Bhaiya I got your Channel 2 days ago.....You are awesome!
the explanation was fantastic , but there issue that you didn't discussed the case when a particular window contains a pattern char for example: str = fffor
pat: for
this was the case which tricked a little :) but rest the explanation was amazing.....
for those who don't get why m[s[i]]==1 then we will do cnt++ because only if m[s[i]] was equal to 0 then only we did cnt-- otherwise cnt remained the same so if m[s[i]]==1 then only we can do cnt++ as earlier we subtracted cnt for it now as the character in no more in our window so m[s[i]]++ and only if m[s[i]]=1 then we increment cnt .
But what is need of that, actually we already check m[s[i]]==0,they we will get our ans na,wht is the need of that last part ,why they again considered a=0,b=0??count =0 can u explain 🥺
Bro your explanation is very easy and good but a little bit of compression is required as video becomes too lengthy.
thanks a lot ADITYA
Much needed topic : Graphs
please try compiling the code in the end, as you did in your earlier videos
// Online C++ compiler to run C++ program online
#include
#include
using namespace std;
int main() {
string str="aabaabaa";
string str2="aaba";
int N=str.size();
int k=str2.size();
int res=0, count=0;
for(int y=0;y
@@umanggupta5803 tysm for the code
@@umanggupta5803 code won't work bro...try: str=bbcc, ptr=ca ..it will give result as 1
class Solution{
public:
int search(string pat, string txt) {
unordered_map mp;
int ans =0;
for(char i : pat) {
if(mp[i]>=1) mp[i]++;
else mp[i]=1;
}
int cnt = mp.size();
int i =0;
int j =0;
int k = pat.size();
while(j
@@umanggupta5803 This logic is wrong. Consider this case where str = "af" and str2 = "be".
Sir you explanation and technique is awesome.
Please make a series on Backtracking and Graph
Eagerly waiting ❤️❤️
Python Solution with the same logic : Leet code problem : 438. Find All Anagrams in a String
from collections import defaultdict
from typing import List
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
ans = []
k = len(p)
map = defaultdict(int)
for ch in p:
map[ch] += 1
count = len(map)
i = 0
j = 0
while j < len(s):
# Calculation:
ch = s[j]
if ch in map:
map[ch] -= 1
if map[ch] == 0:
count -= 1
if j - i + 1 < k:
j += 1
elif j - i + 1 == k:
if count == 0:
ans.append(i)
ch1 = s[i]
if ch1 in map:
map[ch1] += 1
if map[ch1] == 1:
count += 1
i += 1
j += 1
return ans
Can we not use two separate unordered maps to solve this? One for the pattern to be found, the other to store the characters in the current window? We can then simply compare if (patternMap == temporaryMap) and increase the anagram_count accordingly.
Kindly tell me why a single-map approach is preferred? Is it too taxing in terms of space complexity?
O(N) Time complexity code
class Solution{
public:
int search(string pat, string txt) {
// code here
int n = pat.size();
int m = txt.size();
if (m < n) {
return 0;
}
unordered_map m1;
int cnt = 0;
// Initialize the map for the pattern
for (char i : pat) {
m1[i]++;
}
// Initialize the map for the first window in the text
unordered_map m2;
for (int i = 0; i < n; i++) {
m2[txt[i]]++;
}
// Check the first window
if (m1 == m2) {
cnt++;
}
// Process the remaining windows
for (int j = n; j < m; j++) {
// Increment the count for the current character in the window
m2[txt[j]]++;
// Decrement the count for the character at the beginning of the window
m2[txt[j - n]]--;
// Remove the character if its count becomes zero
if (m2[txt[j - n]] == 0) {
m2.erase(txt[j - n]);
}
// Check if the current window is an anagram of the pattern
if (m1 == m2) {
cnt++;
}
}
return cnt;
}
};
🙅🙅🙅
Great Explaination, problem was bit standard
i think brute force would work:
as O( (s-p+1)* 26log26 (comparing 2 maps ) )
for each substring of size P in S : we will keep track of chars count using map
then when substring size == P
compare 2 maps
Here is the go implementation:
package main
import (
"fmt"
"sort"
)
func isEqual(slice1, slice2 []byte) bool {
if len(slice1) != len(slice2) {
return false
}
for idx := 0; idx < len(slice1); idx++ {
if slice1[idx] != slice2[idx] {
return false
}
}
return true
}
func findAnagrams(str1, str2 string) int {
// Basic checks
if len(str1) == 0 || len(str2) == 0 || len(str1) < len(str2) {
return 0
}
// Need to check if the first string has anagrams of second string
// Two strings are anagrams if their sorted strings are same.
str1Byte := []byte(str1)
str2Byte := []byte(str2)
// Sort str2Byte
sort.Slice(str2Byte, func(i int, j int) bool { return str2Byte[i] < str2Byte[j] })
// Create a sliding window of size len(str2)
start := 0
end := 0
num_anagrams := 0
var tmpSlice []byte
for idx:=0; idx < len(str2); idx++ {
end++
}
for end < len(str1Byte) {
// Check if str1Byte[start:end] is an anagram of str2
tmpSlice = append([]byte(nil), str1Byte[start:end]...)
sort.Slice(tmpSlice, func(i int, j int) bool { return tmpSlice[i] < tmpSlice[j] })
if isEqual(tmpSlice,str2Byte) == true {
num_anagrams ++
}
start ++
end ++
}
return num_anagrams
}
func main() {
str1 := "foxxofoxf"
str2 := "fox"
fmt.Println("Input : ", str1)
fmt.Println("Second string : ", str2)
fmt.Println("Number of anagrams = ", findAnagrams(str1, str2))
}
we can calculate the sum of ascii values of the given string and then we can compare that sum with every sliding window and update the counter..
#include
using namespace std;
int main(){
string s;
getline(cin,s);
int n=s.size();
string f;
getline(cin,f);
int count=0;
for(int i=0;i
Na.. this logic is not true always bro..
Input:
text = "zbcoejuvpvaboyg
"
pattern = "po"
Its Correct output is:
0
And Your Code's output is:
1
Here ASCII value sum of "po" is 112+111 = 223
and ASCII value sum of "ju" is 106+117 = 223 too 😬, and these r not anagrams
Ryt 2nd commnt
@@ashishmohapatra4654 right bro
Love ur explanation
mja aaya ! ~ aapka pappu
You are explaining the concepts really lucidly. If possible try to compress the duration of the videos.Little bit cumbersome to watch lengthy videos.
then watch in 2X speed.. he is a great teacher who is teaching everything from basic considering beginners as well.
Bhai TCS me kaam karle usse accha
excellent explanation
Thank you for this video.
Anyone looking for the code. I have implemented it for a similar problem.
LC #438
class Solution(object):
def findAnagrams(self, s, p):
"""
:type s: str
:type p: str
:rtype: List[int]
"""
# make a dict of count of letters
count_letters = {}
for letter in p:
if letter not in count_letters:
count_letters[letter] = 0
count_letters[letter] += 1
total_count = len(count_letters)
k = len(p)
i, j = 0, 0
answer = []
# print(count_letters, total_count)
while j < len(s):
# for j elements
# keep decrementing the count from the dict
# and if it reaches 0, we decrement count by 1
if s[j] in count_letters:
count_letters[s[j]] -= 1
if count_letters[s[j]] == 0:
total_count -= 1
# check if window size is reached
if j - i + 1 < k:
j += 1
elif j - i + 1 == k:
# we have hit the window
# check if count of distinct characters is zero
# if yes, it is an anagram
if total_count == 0:
answer.append(i)
# reverse the calculations done at j so far
# increment the character count
if s[i] in count_letters:
count_letters[s[i]] += 1
if count_letters[s[i]] == 1:
total_count += 1
# slide the window
i += 1
j += 1
return answer
Thnaks yo
can u tell me why we cannot write " if count_letters[s[i]] > 0 " in place of " if count_letters[s[i]] == 1:" before sliding the window
I think you miss one case like when string is abc and bigger string is aaaaaab so when it will calculate count of a it will be negative and will not produce the right output
A check would be needed to make sure the count never goes negative.
Exactly.. I was thinking the same.. Thanks.. U pointed it..
Even if it became negative suppose ptr= aaba i.e.size 4 so for first window our map[a] = -1 as our first window is aaaa but when we will do i++ 4 times then our map[a] becomes 4 again
The question returns the answer.. in this case the answer will never be incremented and thus 0 will be returned which is correct.
can we use ASCII value to check if we got our pattern or not. ASCII value of 'aaab'. i.e. 3 * a + 1 * b
Samajh to question start ke 10 min me hi gya hu. Phir bhi maje le rha hu..😇
Bhaiya what a explanation 👏 👌, mza aa gya yrr, aap jb sumup krne ho na bohot smooth ho jata h sara concepts 💥💯💯
Please bring Playlist for graph and tree Please 🥺🥺
I really appreciate the work you are doing but not coding in editor has it's own disadvantage. One of them is your algos , a few times, give wrong answers and we have to tweak them a lot to get all test cases, which is not good for beginners as it may consume a lot of time.
Anyway, it's a great playlist and explanation is really top level.
bhai agar possible ho to trie ka playlist bana do yarr or ye playlist kya masst explain kiye ho bhai maza a giya
LeetCode 438:
vector findAnagrams(string s, string p) {
unordered_mapm;
vectorv;
for(int i=0;i
this will give WA bro on test case 1
since we are pushing i in the vector v it pushes one extra index in test case 1
why can't we do if(m[s[i]]>0) count++ in the else if condition
it is giving WA on gfg
@@archikashukla7997 !=m.end()) ye kyu kr rhe h ye smjh ni a rha h can u explain me hmm s[i] sirf isse bhi to hm map me check kr skte h na like mp[s[i]] == s[j]
@@archikashukla7997 it's because if s[i] is already in map then we don't need to increase the count, but if s[i] was not present in map (i,e mp[s[i]] == 0 ) then on doing mp[s[i]] ++ we will get mp[s[i]] ==1 , that means a new letter has been mapped so we need to increase the count by 1
@@sohiltr2310nice brother 👍👍👍
Nicely explained
33:36 i think there condition for count++ will be mp[arr[i]] == 1 not count==1
Please do permutation in string as well on leetcode to get good hands on variation, and suggest if similar problems are there to work with variation in this type of questions.......
It can be surely explained in 15minutes
Unnecessary repeating for 20 minutes
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
k = len(p)
hashMap = {}
for char in p:
if char in hashMap:
hashMap[char] += 1
else:
hashMap[char] = 1
count = len(hashMap)
i, j = 0, 0
ans = []
while j < len(s):
# Calculation
if s[j] in hashMap:
hashMap[s[j]] -= 1
if s[j] in hashMap and hashMap[s[j]] == 0:
count -= 1
# When window is smaller
if j - i + 1 < k:
j += 1
# When window size is equal
elif j - i + 1 == k:
# get the answer
if count == 0:
ans.append(i)
# revert the operation for the first element of the window to remove it from the answer
# before sliding the window
if s[i] in hashMap:
hashMap[s[i]] += 1
if hashMap[s[i]] == 1:
count += 1
i += 1
j += 1
return ans
Thankyou so much sir , i am able to write my own code ..
thnq keep up the good work
you have explained about, increasing count++, if removing element (arr[i++]) present in hashmap while sliding,
but what about the new element which will added to the window ?
suppose, Str = "foroffroofr";
and ptr = "for";
1). first window "for", all count in map will be zero and count variable also will be zero.
2). second window we are removing 'f' and adding 'o' then window becomes "oro".
In above case count of 'f' in hashmap will become 1, and count variable also becomes 1, but what should be done for adding element 'o' ? because 'o' count in hashmap is already zero so if we decrease it it will become -1.
3) third window "rof", this is creating problem for me.
so can you please iterate over this and explain ?
only increment counter when the count of character in the map is greater than zero
you are the best
✨🔥 You are awsome bhaiya ! #support
Those who are wondering for the c++ code here it is exact code....
void solve() {
int n; cin >> n;
string s, t; cin >> s >> t;
mapmp;
int ans = 0;
for (auto c : t)mp[c]++;
int i = 0, j = 0, count = mp.size();
while (j < n) {
if (mp.find(s[j]) != mp.end()) {
mp[s[j]]--;
if (!mp[s[j]])count--;
}
if (j - i + 1 < sz(t)) {
j++;
}
else if (j - i + 1 == sz(t)) {
if (!count) {
ans++;
}
if (mp.find(s[i]) != mp.end()) {
mp[s[i]]++;
if (mp[s[i]] == 1)count++;
}
i++; j++;
}
}
cout
Eagerly waiting for Linked list videos
thank you so much😇
#include
using namespace std;
int main() {
string s, t;
cin >> s >> t;
int k = t.size();
map mpp, mpp1;
// Populate frequency map for string t
for (char ch : t) {
mpp[ch]++;
}
int i = 0, c = 0;
int j = 0;
while (j < s.size()) {
mpp1[s[j]]++; // Add current character to mpp1
// Check if we have a window of size k
if (j - i + 1 == k) {
// Compare frequencies of characters
bool match = true;
for (auto& entry : mpp) {
if (mpp1[entry.first] != entry.second) {
match = false;
break;
}
}
if (match) {
c++;
}
// Slide the window
mpp1[s[i]]--; // Remove character going out of window
i++;
}
j++;
}
cout
Great Explaination vro! I found the code in discussion forums but did not get the explaination specially why left pointer moving forward (should decrease the map ) but is increasing. But finaaly i have my fog cleared up!
I have the same doubt? Can you please explain to me?
Thanks for a very good explanation. Similar logic is used in LC 205: Are isomorphic strings?
its diff
Python code for Count Occurences
from collections import Counter
class Solution:
def search(self, pat, txt):
# Initializing pointers and variables
i = 0
j = 0
n = len(txt)
k = len(pat)
ans = 0
# Create a hashmap with the frequency of characters in the pattern
hash_map = Counter(pat)
count = len(hash_map)
# Sliding window
while i < n:
if txt[i] in hash_map:
hash_map[txt[i]] -= 1
if hash_map[txt[i]] == 0:
count -= 1
if i - j + 1 < k:
i += 1
elif i - j + 1 == k:
if count == 0:
ans += 1
if txt[j] in hash_map:
if hash_map[txt[j]] == 0:
count += 1
hash_map[txt[j]] += 1
j += 1
i += 1
return ans
At 23:06 the condition of >0 is wrong because if freq of a char was increasing from 2 to 3 then also count would get updated which is wrong
int search(string pat, string txt) {
int i = 0, j = 0;
int k = pat.length();
int patSum = 0; // Sum of ASCII values of characters in the pattern
int currSum = 0; // Sum of ASCII values of characters in the current window
// Calculate the sum of ASCII values of characters in the pattern
for (int i = 0; i < k; i++) {
patSum += pat[i];
}
int ans = 0; // Counter for occurrences
while (j < txt.size()) {
currSum += txt[j];
if (j - i + 1 < k) {
j++;
} else if (j - i + 1 == k) {
if (currSum == patSum) {
ans++;
}
currSum -= txt[i];
i++;
j++;
}
}
return ans;
} why this fail, can anyone explain
if i use this method instead of map
Ascii of a+d = ascii of b+c, but ad ain't equal to bc
@@btcdivine yess got it, my intutuion was so naive lol, thankyouu.
can we use multiset instead of multimap??
Leetcode sol - 438
class Solution {
public:
vector findAnagrams(string s, string p) {
vectorans;
int k = p.size();
unordered_map mp;
// storing the occurence of string p in map
for(int i=0; i
Nice explanation. What software are you using to write and draw? looks pretty good.
apple hai bhai
ababbaba Let's say It's string ptr= abab
So when we slide the window b value is going at negative -1?
It's it ok?