Это видео недоступно.
Сожалеем об этом.
Count Occurrences Of Anagrams | Sliding Window
HTML-код
- Опубликовано: 19 авг 2024
- Patreon Link: / adityaverma
Video Pdf Notes And Code: / 43529429
Playlist Link: • Sliding Window Algorit...
Problem Description: practice.geeks...
Given a word pat and a text txt. Return the count of the occurences of anagrams of the word in the text.
Example 1:
Input:
txt = forxxorfxdofr
pat = for
Output: 3
Explanation: for, orf and ofr appears
in the txt, hence answer is 3.
Example 2:
Input:
txt = aabaabaa
pat = aaba
Output: 4
Explanation: aaba is present 4 times
in txt. .
------------------------------------------------------------------------------------------
Here are some of the gears that I use almost everyday:
🖊️ : My Pen (Used in videos too): amzn.to/38fKSM1
👨🏻💻 : My Apple Macbook pro: amzn.to/3w8iZh6
💻 : My gaming laptop: amzn.to/3yjcn23
📱 : My Ipad: amzn.to/39yEMGS
✏️ : My Apple Pencil: amzn.to/3kMnKYf
🎧 : My Headphones: amzn.to/3kMOzM7
💺 : My Chair: amzn.to/385weqR
🛋 : My Table: amzn.to/3kMohtd
⏰ : My Clock: amzn.to/3slFUV3
🙋🏻♀️ : My girlfriend: amzn.to/3M6zLDK ¯\_(ツ)_/¯
PS: While having good gears help you perform efficiently, don’t get under the impression that they will make you successful without any hard work.
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 😂😂😂
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
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
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 👍
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
The question came in a Codechef contest yesterday, couldn't think of this approach. The video helps a lot in up-solving thanks :)
#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...
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
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!
It can be surely explained in 15minutes
Unnecessary repeating for 20 minutes
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
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
Bro.. very good 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
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.
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. 😍😍😍😍
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.
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
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;
};
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;
}
}
Thank You bhaiya
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
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;
Aditya: Video faltu mai lamba ho jata h
Also Aditya : video length 40 Min
love your work man!!!
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
blessed to have found your channel
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".
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
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.
Hats off guru.... Apke concept faad hai... Bahot saare question solve ho rahe hai ab... Bahot Bahot dhanyabaad
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
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
Please do complete this series!Keep up the good work👍
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
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
This guy is a genius
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.....
int search(string pat, string text) {
// code here
//sliding window problem
int n=text.size();
int k=pat.size();
mapmp1;
for(int i=0;i
Thank you fir this!
Nice explanation man, could solve by myself, halfway through the video.
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
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 ?
Great explanation Sir. LC 438 is a similar question which I could solve easily by your approach in above question.
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 👍👍👍
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
Bro your explanation is very easy and good but a little bit of compression is required as video becomes too lengthy.
#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
Love your recursion and dp playlist brother
👌
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;
}
};
🙅🙅🙅
Thank you bhaiya. Concept puri tarah se chamak gya.
Thank you very much. You are a genius.
Java solution: passed all tc of geekforgeek
public class AllAnargamInString {
public static void main(String[] args) {
String s = "forxxorfxdofr";
String ptr = "for";
int count = search(ptr, s);
System.out.println(count);
}
private static int search(String ptr, String s) {
Map m = new HashMap();
for (char ch : ptr.toCharArray()) {
if (m.containsKey(ch))
m.put(ch, m.get(ch) + 1);
else
m.put(ch, 1);
}
int count = m.size();
int strSize = s.length();
int k = ptr.length();
int i = 0;
int j = 0;
int ans = 0;
while (j < strSize) {
char jth = s.charAt(j);
if (m.containsKey(jth)) {
m.put(jth, m.get(jth) - 1);
if (m.get(jth) == 0)
count--;
}
if (j - i + 1 < k)
j++;
else if (j - i + 1 == k) {
if (count == 0)
ans++;
char start = s.charAt(i);
if (m.containsKey(start)) {
m.put(start, m.get(start) + 1);
if (m.get(start) == 1)
count++;
}
i++;
j++;
}
}
return ans;
}
}
cpp code :
class Solution{
public:
int search(string pat, string txt) {
int i =0,j =0;
int ans = 0;
map mp;
int k = pat.size();
for(int i=0;i
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
bahut badhiya yaar badi mehnat ka kaam hai. Thank you.
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
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 🥺
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
dude!! your explanation is amazing...
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
thanks a lot ADITYA
thanks you are finally back!!😊
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.
can we use ASCII value to check if we got our pattern or not. ASCII value of 'aaab'. i.e. 3 * a + 1 * b
maza a gaya maza a gaya bhaiya.
upar jo ho raha thik uska ulta niche ho raha.
//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
thank u so much for uploading such an awsm content ....seems like i really found a gem
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))
}
Samajh to question start ke 10 min me hi gya hu. Phir bhi maje le rha hu..😇
It was awesome! Its always fun to watch your videos
leetcode problems for the same
1) task: leetcode.com/problems/find-all-anagrams-in-a-string/
soln: leetcode.com/submissions/detail/799948812/
2) task: leetcode.com/problems/permutation-in-string/
soln: leetcode.com/submissions/detail/799946580/
i love the way you teach
Code in C++
class Solution{
public:
int search(string pat, string txt) {
// code here
int n = pat.size();
int m = txt.size();
map m1;
map m2;
int cnt = 0;
for(auto i:pat){
m1[i]++;
}
int i=0,j=0;
while(j
LC - 567,438,1876
he is good, but information is repetitive which prolongs the video.
Graphs please :)
Sir you explanation and technique is awesome.
Please make a series on Backtracking and Graph
Eagerly waiting ❤️❤️
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 🥺🥺
What a brilliant man🎉
Sir I have implemented in a little bit different way. Will it work for all test cases.
#code
def CountAnagram(strng, pattern, n):
k = len(pattern) #window size
start = 0
end = 0
ans = 0
while end < n:
if((end - start + 1) < k):
end += 1
elif ((end-start + 1) == k):
curr_anagram = strng[start:end+1]
if(sorted(curr_anagram) == sorted(pattern)):
ans += 1
start += 1
end += 1
return ans
s = "aabaabaa"
pattern = "aaba"
n = len(s)
print(CountAnagram(s, pattern, n))
Love ur explanation
Thankyou so much sir , i am able to write my own code ..
mindblowing explanation 💥
Much needed topic : Graphs
//very simple cpp code
#include
#include
#include
#include
#include
using namespace std;
int main() {
// your code goes here
string str; getline(cin,str); int n1 = str.length();
string str2; getline(cin,str2); int n2 = str2.length(), count=0;
sort(str2.begin(),str2.end());
string temp;
for(int i = 0; i
How will we identify if a question can be solved via sliding window or dynamic programming
There are many ways but one of the most obvious ones is the length of input provided. If the input is >= 10^5 then don't use DP. If it is less than that then the interviewer wants u to solve it with DP. But the sliding window is always better.
Bro, please make Graphs' playlist now, I think everyone is waiting for it more than any other topic, after watching the DP series, and it is the placement season as well so it will be very handy for us if you can make it now asap.
Bhaiya I got your Channel 2 days ago.....You are awesome!
just used hashing of characters to store cnt of each character in vector
#another_approch_little_modification
class Solution{
public:
int search(string str, string s)
{
vectorhsh1(26);
vectorhsh2(26);
for(int i=0;i
can we use multiset instead of multimap??
bhaia please provide the code for the above explanation ....I'm still getting stucked
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
@@vaibhavtiwari9712 its of which leetcode question bro?
@@gautamarora6556 find all anagram in a string question no 438
excellent explanation
Working code JAVA, gfg all test cases passing. Thankyou Aditya bhaiya
thx man
Can this be considered as efficient algorithm having complexity of O(n * m log(m)) where m is the size of the string be matched and n is the size of the larger string.
string s1, s2;
cin >> s1 >> s2;
sort(s2.begin(), s2.end());
int i = 0, j = 0;
int n = s1.size();
int nn = s2.size();
int ans = 0;
while(j
is it getting accepted?
this is basically n ^ 2 and this can be solved in order n
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.......
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
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?
Nicely explained
Bro waiting for backtracking series
thank you so much😇