Count Occurrences Of Anagrams | Sliding Window
Вставка
- Опубліковано 1 жов 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.
#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...
Dude you are the best !! Please complete this series asap .Eagerly waiting for backtracking and graph
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
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
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!
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!
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
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
Bro.. very good explanation
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
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 👍👍👍
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;
}
}
The question came in a Codechef contest yesterday, couldn't think of this approach. The video helps a lot in up-solving thanks :)
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
int search(string pat, string txt) {
// code here
mapmp,SlidingMp;
int cnt=0;
int pLen=pat.length();
int tLen=txt.length();
for(int i=0;i
he is good, but information is repetitive which prolongs the video.
Please help....Why is this not working...
class Solution{
public:
int search(string pat, string txt) {
int patSum =0;
for(int i=0 ; i
#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
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
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.
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
Python Code:
class Solution:
def search(self,pat, txt):
i,j,ans=0,0,0
K,N = len(pat),len(txt)
m = {}
for l in pat:
m[l]=m.get(l,0)+1
c=len(m)
while j
Graphs please :)
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
what is the name of this application on which you are writing?
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 ?
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;
}
}
can we use ASCII value to check if we got our pattern or not. ASCII value of 'aaab'. i.e. 3 * a + 1 * b
int search(string txt, string pat) {
unordered_map mp;
for(auto it: txt)mp[it]++;
int size = pat.length();
int len = mp.size();
int i=0;
int j=0;
int k = txt.length();
int ret_count=0;
unordered_map mp2;
while(jsecond)
{
char_count++;
it++;
}
if(char_count==len)
ret_count++;
}
mp2[pat[i]]--;
i++;
j++;
}
}
return ret_count;
}
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
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".
It can be surely explained in 15minutes
Unnecessary repeating for 20 minutes
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 👍
//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
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
Aditya: Video faltu mai lamba ho jata h
Also Aditya : video length 40 Min
love your work man!!!
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. 😍😍😍😍
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.....
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
var I=0; j=0; list =[];
while(j
Easiest C++ Code
class Solution{
public:
int search(string pat, string txt) {
int ans=0;
vector curr_patt_char(26,0);
vector pat_char(26,0);
int m=pat.size();
int n=txt.size();
for(int i=0;i
Bro waiting for backtracking series
can any please correct my code it giving 0 as answer always
int search(string pat, string txt) {
int p[26]={0};int t[26]={0};
const char *s = pat.c_str(); int len=0;
while (*s)
{
p[*s-'a']++;
s++; len++;
}
int count=0; int flag=1;
const char *x = txt.c_str(); int lent=0; const char *first = txt.c_str();
while(*x)
{
t[*x-'a']++;
if(lent>=len) { flag=1;
for(int row=0;row
Bhai backtracking aur graph pr video chahiye yrr . please upload it dijiye
code:
public:
int search(string pat, string txt) {
// code here
map mp;
for(int i=0; i
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
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;
};
blessed to have found your channel
LC - 567,438,1876
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
//Java leetcode submission :
class Solution {
public List findAnagrams(String s, String p) {
char[] arr2 = p.toCharArray();
int k = arr2.length;
HashMap map = new HashMap();
for (char ch : arr2) {
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
int count = map.size();
int i = 0;
char[] arr = s.toCharArray();
List ans = new ArrayList();
for (int j = 0; j < arr.length; j++) {
if (map.containsKey(arr[j])) {
int val = map.get(arr[j]);
if (val == 1) count--; // value is going to be decrease to 0 in next step
map.put(arr[j], val - 1);
}
if (j - i + 1 == k) {
if (count == 0) ans.add(i);
if (map.containsKey(arr[i])) {
int val = map.get(arr[i]);
if (val == 0) count++; // value is going to be increase from 0 next step
map.put(arr[i], val + 1);
}
i++;
}
}
return ans;
}
}
In case when we encountered with some foreign character ( which is not a part of pattern) then the whole evaluation variables need to reset
like resetting map and count
I didn't find it convered in video
Edit : I got the gist as there is foreign element come in between and we have window constraint that will eventually make it reset as i++ takes over
//{ Driver Code Starts
#include
using namespace std;
// } Driver Code Ends
//User function template for C++
class Solution{
public:
int search(string pat, string txt) {
// code here
int count = 0;
unordered_mappattern;
unordered_maptext;
for(auto c : pat){
pattern[c]++;
}
int i=0;
int j=0;
int k=pat.length();
while(j> t;
while (t--) {
string pat, txt;
cin >> txt >> pat;
Solution ob;
auto ans = ob.search(pat, txt);
cout
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/
GFG VIDEO CPP CODE (Need Help)
Idk why its not working on test case :
I/P :
str : kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkk
pat :kkkk
O/P = 33
Original O/P = 37
class Solution{
public:
int search(string pat, string txt) {
int k = pat.length();
int n = txt.length();
unordered_map mp;
for(int i=0;i
class Solution{
public:
int search(string pat, string txt) {
unordered_mapmap;
for(int i=0;i
JAVA:-
int search(String pat, String txt) {
// code here
Map map = new HashMap();
for(int i=0;i
//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
My solution
int search(string pat, string txt)
{
vector patF(26, 0);
vector txtF(26, 0);
int ans = 0;
for (int i = 0; i < pat.size(); i++)
{
patF[pat[i] - 'a']++;
}
int k = pat.size();
for (int i = 0; i < k; i++)
{
txtF[txt[i] - 'a']++;
}
if (patF == txtF)
{
ans++;
}
int left = 0;
int right = k;
while (right < txt.size())
{
txtF[txt[left] - 'a']--;
left++;
txtF[txt[right] - 'a']++;
right++;
if (patF == txtF)
{
ans++;
}
}
return ans;
}
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?
int search(string pat, string txt) {
map mp;
for (int i = 0; i < pat.size(); i++) {
mp[pat[i]]++;
}
int ans = 0;
int cnt = mp.size(); // number of unique characters to be matched
int i = 0, j = 0;
while (j < txt.size()) {
// Decrement count of current character
if (mp.find(txt[j]) != mp.end()) {
mp[txt[j]]--;
if (mp[txt[j]] == 0) {
cnt--; // One unique character completely matched
}
}
// Check if window size is less than the size of the pattern
if (j - i + 1 < pat.size()) {
j++;
}
// When window size matches the size of the pattern
else if (j - i + 1 == pat.size()) {
if (cnt == 0) {
ans++;
}
// Slide the window
if (mp.find(txt[i]) != mp.end()) {
if (mp[txt[i]] == 0) {
cnt++; // One unique character is no longer completely matched
}
mp[txt[i]]++;
}
i++;
j++;
}
}
return ans;
}
Cant we sum the characters in pattern and sum of the window . If they are equal, then increase counter??
LEETCODE 438. Find All Anagrams in a String(JAVA CODE)
class Solution {
public List findAnagrams(String s, String p) {
List res = new ArrayList();
int k = p.length();
Map map = new HashMap();
for (int i = 0; i < k; i++) {
char ch = p.charAt(i);
map.put(ch, map.getOrDefault(ch, 0) + 1);
}
int i = 0;
int j = 0;
int count = map.size();
while (j < s.length()) {
char endChar = s.charAt(j);
if (map.containsKey(endChar)) {
map.put(endChar, map.get(endChar) - 1);
if (map.get(endChar) == 0) {
count--;
}
}
if (j - i + 1 < k) {
j++;
} else if (j - i + 1 == k) {
if (count == 0) {
res.add(i);
}
char startChar = s.charAt(i);
if (map.containsKey(startChar)) {
if (map.get(startChar) == 0) {
count++;
}
map.put(startChar, map.get(startChar) + 1);
}
i++;
j++;
}
}
return res;
}
}
what if the character in the string does not exist in pattern? in that case traversing map might b required..
//Hello Bhaya ye mene kiya khud se but isme TLE aarhi h GFG par kya aap is code ko review kar k bata sakte ho kya me kaha par optimize karu..
// User function Template for Java
class Solution
{
int search(String pat, String txt)
{
// code here
char[] text = txt.toCharArray();
char[] x = pat.toCharArray();
int n = text.length;
int k = x.length;
// Arrays.sort(text);
Arrays.sort(x);
int count = 0;
for(int i = 0; i
unordered_mapmp;
for(auto x : pat){
mp[x]++;
}
int k = pat.length();
int count = mp.size();
int res = 0;
//sliding window
int i = 0;
int j = 0;
while(j
bhaiya App jab padate ho ek overconfidence wala attitude dikh ta hai jab aa samjate ho,
plz thoda lightly and humble tarike se samjhaya kariye.
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
Bro your explanation is very easy and good but a little bit of compression is required as video becomes too lengthy.
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.
Java Code
class Solution {
int search(String pat, String txt) {
MapHelper helper = new MapHelper(pat);
int n = txt.length(); //Size of string
int k= pat.length(); //window size
int i=0;
int j=0;
int ans = 0;
while(j
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
leetcode 438
class Solution {
public:
vector findAnagrams(string s, string p) {
unordered_mapmp;
for(int i=0;i
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
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
Samajh to question start ke 10 min me hi gya hu. Phir bhi maje le rha hu..😇
bro har 10 sec me ad aa rahi hai. itni bhi kya greed
can we use multiset instead of multimap??
Bhai na kahi written question, na koi ide, insaan check kaise kre apna solution
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.
any one here plz comment me brute and optimal approach java code
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
int search(string pat, string txt) {
vectorp(26,0) , t(26,0);
for(int i =0 ; i < pat.size() ; i++){
p[pat[i]-'a']++;
}
int i = 0, j = 0;
while(j-i+1 != pat.size()){
t[txt[j++]-'a']++;
}
int ans = 0;
for(i,j ; j < txt.size() ; i++,j++){
t[txt[j]-'a']++; // compute for last
if(p == t) ans++; // compare for answer
t[txt[i]-'a'] = max(0, --t[txt[i]-'a']); // undo before going ahead
}
return ans;
}
when keeping the list, before checking, j will be pointing to last window element. so before comparison do the computation for tat.. after compairing, we will be moving with the window so undo or reverse changes done for i'th.
#include
#include
#include
using namespace std;
// Function to count the occurrences of anagram of a string in another string
int countAnagramOccurrences(const string& str, const string& pattern) {
map patternCount;
map windowCount;
int patternLength = pattern.length();
int windowLength = str.length();
// Count the occurrences of each character in the pattern
for (char c : pattern) {
patternCount[c]++;
}
int count = 0;
int left = 0;
int right = 0;
// Sliding window technique to iterate over the string
while (right < windowLength) {
// Expand the window by adding the rightmost character
windowCount[str[right]]++;
// Shrink the window if its size exceeds the pattern length
if (right - left + 1 > patternLength) {
windowCount[str[left]]--;
if (windowCount[str[left]] == 0) {
windowCount.erase(str[left]);
}
left++;
}
// Check if the window is an anagram of the pattern
if (windowCount == patternCount) {
count++;
}
right++;
}
return count;
}
int main() {
string str = "abcbacab";
string pattern = "abc";
int occurrenceCount = countAnagramOccurrences(str, pattern);
cout
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.
clean code c++
#include
using namespace std;
int main()
{
string s, s1;
cin >> s >> s1;
map m;
for (auto val : s1)
{
m[val]++;
}
int i = 0, j = 0, count = m.size(), ans = 0, windowsize = s1.size();
while (i < s.size())
{
if (m.count(s[i])) // if element exist in s1
{
m[s[i]]--;
if (m[s[i]] == 0) // condtion to decrease count
count--;
}
if (i - j + 1 < windowsize) // condtion to incraese element in window
i++;
else
{
if (count == 0) // if windowsize== angram size and count==0
ans++;
if (m.count(s[j]))
{
m[s[j]]++;
if (m[s[j]] == 1) // condtion to increase count when count > 0
count++;
}
i++, j++;
}
}
cout
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))
}
I hope it will help you..!!
class Solution{
public:
int search(string pat, string txt) {
// code here
int i=0,j=0,k=pat.size(),ans=0;
map mp;
for(auto it : pat){
mp[it]++;
}
int cnt=mp.size();
while(j
int search(string pat, string txt) {
int n=txt.length();
int m=pat.length();
vectorv1(27,0),v2(27,0);
for(int i=0;i
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
Why don't we do one thing
1. I will create all anagrams of the given pattern and hash it somewhere
2. After my window size hit we just need to find the substring between i and j
3. Check this substring present in the hash or not
4 if yes then we can increment our count
So simple no need to find all the stuff I mean counting of character and others I will easily forgot this .
Correct me If I am wrong, I am also learning.
Leetcode-438
code-(in java)
class Solution {
public List findAnagrams(String s, String p) {
List list = new ArrayList();
Map map = new HashMap();
for(char c : p.toCharArray()){
map.put(c, map.getOrDefault(c,0)+1);
}
int size = map.size();
int m = s.length();
int n = p.length();
int i=0,j=0;
while(j
int search(string pat, string txt) {
int ans = 0;
unordered_map m;
int pLen = pat.size();
int tLen = txt.size();
for( int i=0; i
GFG accepted java code :)
HashMap map = new HashMap();
for (int i = 0; i < pat.length(); i++) {
char ch = pat.charAt(i);
if (map.containsKey(ch)) {
map.put(ch, map.get(ch) + 1);
} else {
map.put(ch, 1);
}
}
int count = map.size();
int k = pat.length();
int i = 0, j = 0, ans = 0;
while (j < txt.length()) {
char end = txt.charAt(j);
if (map.containsKey(end)) {
map.put(end, map.get(end) - 1);
if (map.get(end) == 0) {
count--;
}
}
if ((j - i + 1) < k) {
j++;
} else if ((j - i + 1) == k) {
if (count == 0) {
ans++;
}
char start = txt.charAt(i);
if (map.containsKey(start)) {
map.put(start, map.get(start) + 1);
if (map.get(start) == 1) {
count++;
}
}
i++;
j++;
}
}
return ans;
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
String sr1= "aabaabaa";
String sr2= "aaba";
int k= sr2.length();
int i=0;
int j=0;
int ans=0;
HashMap map= new HashMap();
for(int p=0;p
javascript solution :-
let string = "forrofoo"
let pat = "for"
function solve(string,pat) {
let map = new Map()
for(let i = 0; i