great video. one question. We are comparing 2 hashmaps pmap and sMap inside a while loop. Even though assuming it is a ascii , there could be 256 keys in each map max. would that not degrade performance. While still O(n), will it not be actually O(256 *n) time complexity?
your time complexity is O( length of s * length of p) but it can easily be solved in O( length of s ) + O( length of p ) . here is the code public static List findAnagrams(String s, String p) { List ans = new ArrayList(); HashMap map2 = new HashMap(), map1 = new HashMap(); for (int i = 0; i < p.length(); i++) { map2.put(p.charAt(i), map2.getOrDefault(p.charAt(i), 0) + 1); } int i = -1, j = -1; while (true) { boolean f1 = false, f2 = false; while (j < s.length() - 1) { f1 = true; j++; char ch = s.charAt(j); map1.put(ch, map1.getOrDefault(ch, 0) + 1); if (!map2.containsKey(ch) || map1.get(ch) > map2.get(ch)) break; if (j - i == p.length()) ans.add(i + 1); } while (i < j) { i++; f2 = true; char ch = s.charAt(i); map1.put(ch, map1.getOrDefault(ch, 0) - 1); if (map1.get(ch)
that O(n) considers 26 as constant so the loop runs for checking isn't considered , here too hashmap would only have 26 entries at max so if the input ins't in millions ,there's no difference in performance of this and that solution
@@glean56 but it's a constant space of 26 key value pair , so it won't matter much , although array can be better option due to cache friendliness but it doesn't make much difference using any of them
sir do you have any list of questions to prepare for interviews? the most commonly asked interview questions to prepare to answer any question from knowing those basic questions?
You need to check base conditions otherwise test cases will fail. Example : lines 24-27 will fail if pattern's length is greater than that of source string's length. if (s == null || s.length() == 0 || p == null || p.length() == 0 || s.length() < p.length())
sir jab jab window hit hogi to dono hashmap apn check kar rahe he ki barabar he ya nahi agar window hi baht badi hui to dono hashmaps ko compare jo apn kar rahe he usme time nahi lagega!! and space b lag rahi h do hashmaps use karne se!!!
#include #include #include using namespace std; vector arr; void removeFromMap(map &m, char ch) { if (m[ch] == 1) m.erase(ch); else m[ch]--; } int count(string &s1, string &s2) { int n1 = s1.length(); int n2 = s2.length(); map m1; map m2; // pattern map of string-s2 for (auto &val : s2) m2[val]++; int cnt = 0, i = -1, j = -1; while (true) { bool f1 = false, f2 = false; // acquire while (i < n1 - 1) { f1 = true; i++; m1[s1[i]]++; // we need to maintain a window-size equal to that of the s2-length if (i - j == n2) break; } // release while (j < i) { f2 = true; if (m1 == m2) { cnt += 1; arr.push_back(j + 1); } j++; removeFromMap(m1, s1[j]); // as soon as the window-size is becomes less than the s2-length // stop releasing if (i - j < n2) break; } if (f1 == false && f2 == false) break; } return cnt; } int main() { string s1, s2; cin >> s1 >> s2; cout
Leetcode AC Solution : class Solution { public boolean check(int a[], int b[]) { for(int i = 0; i < 26; i ++) { if(a[i] != b[i]) return false; } return true; } public List findAnagrams(String s, String p) { int arr[] = new int[26]; List ans = new ArrayList(); for(int i = 0 ; i < p.length(); i ++) arr[p.charAt(i) - 'a'] ++; int start = 0, end = 0; int ch[] = new int[26]; while(end < s.length()) { ch[s.charAt(end) - 'a'] ++; if(end < p.length()-1) end ++; else { if(check(ch, arr)) ans.add(start); ch[s.charAt(start) - 'a'] --; start ++; end ++; } } return ans; } }
O(n), n being the size of source string, comparison function runs in constant time as atmost 26 comparisons will be done as only these many alphabets are there.
Complete Java Code: class Solution { private boolean compareMaps(HashMap sMap, HashMap pMap){ for(Map.Entry entry: pMap.entrySet()){ char key = entry.getKey(); int val = entry.getValue(); if(!sMap.containsKey(key) || sMap.get(key) != val){ return false; } } return true; } public List findAnagrams(String s, String p) { List result = new ArrayList(); if (s.length() < p.length()) { return result; // No possible anagrams if the length of p is greater than the length of s } HashMap sMap = new HashMap(); HashMap pMap = new HashMap(); for(int i = 0; i < p.length(); i++){ sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1); pMap.put(p.charAt(i), pMap.getOrDefault(p.charAt(i), 0) + 1); } int j = 0, i = p.length(); while (i < s.length()) { int index = i - p.length(); if (compareMaps(sMap, pMap)) { result.add(index); } char ch = s.charAt(i); sMap.put(ch, sMap.getOrDefault(ch, 0) + 1); char prevChar = s.charAt(index); int val = sMap.get(prevChar); if (val == 1) { sMap.remove(prevChar); } else { sMap.put(prevChar, val - 1); } i++; // Increment i to move the sliding window } // Check if the last window is an anagram if (compareMaps(sMap, pMap)) { result.add(i - p.length()); } return result; } }
WHATS WRONG WITH THIS ONE IF THE TEST CASE. (GEEKSFORGEEKS) class Solution { public boolean compare(HashMap pmap,HashMap smap){ for(char srcCh: smap.keySet()){ if(pmap.getOrDefault(srcCh,0)!=smap.get(srcCh)){ return false; } } return true; } int search(String p, String s) { HashMap smap = new HashMap(); HashMap pmap = new HashMap(); for(int i =0;i
If your leetcode test cases are failing just use smap.equals(pmap) condition instead of the compare method which sir created.
Yes you are right but why did this happen....I mean what is wrong with the compare method which sir created?
@@youngshahrukhkhan8179 i have the same doubt sirs code is working for all testcases except the last 3 to 5 test cases in leetcode
thanks man I was stuck for 1 hr on this before seeing ur comment
thanks for your suggestion, I was stuck in this.
Thank you prateek..Only 2 test cases were not giving right answer but with equals they ran.
This playlist is literally gold , crystal clear explanation . Thankyou so much sumeet sir
Thank you, sir aapne acquire and release ki strategy kaafi achi batayi ..simply it's awesome...
great video. one question. We are comparing 2 hashmaps pmap and sMap inside a while loop. Even though assuming it is a ascii , there could be 256 keys in each map max. would that not degrade performance. While still O(n), will it not be actually O(256 *n) time complexity?
your time complexity is O( length of s * length of p) but it can easily be solved in O( length of s ) + O( length of p ) .
here is the code
public static List findAnagrams(String s, String p) {
List ans = new ArrayList();
HashMap map2 = new HashMap(), map1 = new HashMap();
for (int i = 0; i < p.length(); i++) {
map2.put(p.charAt(i), map2.getOrDefault(p.charAt(i), 0) + 1);
}
int i = -1, j = -1;
while (true) {
boolean f1 = false, f2 = false;
while (j < s.length() - 1) {
f1 = true;
j++;
char ch = s.charAt(j);
map1.put(ch, map1.getOrDefault(ch, 0) + 1);
if (!map2.containsKey(ch) || map1.get(ch) > map2.get(ch)) break;
if (j - i == p.length()) ans.add(i + 1);
}
while (i < j) {
i++;
f2 = true;
char ch = s.charAt(i);
map1.put(ch, map1.getOrDefault(ch, 0) - 1);
if (map1.get(ch)
sliding window solves it in O(n) , with an array of size of 26 (in this case). Comparing two hashmaps seems redundant
that O(n) considers 26 as constant so the loop runs for checking isn't considered , here too hashmap would only have 26 entries at max
so if the input ins't in millions ,there's no difference in performance of this and that solution
@@mickyman753 hashmap also has space penalty.
@@glean56 but it's a constant space of 26 key value pair , so it won't matter much , although array can be better option due to cache friendliness but it doesn't make much difference using any of them
sir do you have any list of questions to prepare for interviews? the most commonly asked interview questions to prepare to answer any question from knowing those basic questions?
Simply awesome sir.. learning a lot from you sir.. 😍❤️ Can't be thankful enough sir
It's my pleasure
You need to check base conditions otherwise test cases will fail. Example : lines 24-27 will fail if pattern's length is greater than that of source string's length.
if (s == null || s.length() == 0 || p == null || p.length() == 0 || s.length() < p.length())
leetcode test cases are failing
even after handling the case of s < p
then also test cases are failing
If your leetcode test cases are failing just use smap.equals(pmap) condition instead of the compare method which sir created.
itna bada comapre function kyo likha sir ji sida sida smap.equals(pmap)) se bhi kaam chl jata
Isi technique ko sliding window Kehte he kya?
We can directly use equals method of hashmap
Agreed
Finally I got this channel after watching sumit sir in singh in USA channel
Welcome, aboard. Keep learning
Thanks sir,I learned a lot from this video.
Glad you liked it!
Keep learning.
And for better experience and well organised content visit nados.pepcoding.com
Great Explanatiion sir
#Pepcoding Hi Sir, Is it the best solution when considering the time and space complexity?
No it is not. The best solution will require a single hasmap only.
you can use a character array of 26 letters, instead of hashmap
sir jab jab window hit hogi to dono hashmap apn check kar rahe he ki barabar he ya nahi agar window hi baht badi hui to dono hashmaps ko compare jo apn kar rahe he usme time nahi lagega!! and space b lag rahi h do hashmaps use karne se!!!
my cpp code using two hashmaps:
class Solution {
public:
bool comp(unordered_maptext,unordered_mappat)
{
if(text==pat)
return true;
return false;
}
vector findAnagrams(string s, string p) {
vectorv;
unordered_maptext;
unordered_mappat;
for(int i=0;i
sir can u share .any platform ..where we can contact you regarding our doubts because its difficult you can reply on comments!!
telegram
t.me/pepcoding
Sir aake cpp editor me function nai likhe the jaise java me likhe hote hai
beta likhwa rha hun ajkal
#include
#include
#include
using namespace std;
vector arr;
void removeFromMap(map &m, char ch) {
if (m[ch] == 1)
m.erase(ch);
else
m[ch]--;
}
int count(string &s1, string &s2) {
int n1 = s1.length();
int n2 = s2.length();
map m1;
map m2;
// pattern map of string-s2
for (auto &val : s2)
m2[val]++;
int cnt = 0, i = -1, j = -1;
while (true) {
bool f1 = false, f2 = false;
// acquire
while (i < n1 - 1) {
f1 = true;
i++;
m1[s1[i]]++;
// we need to maintain a window-size equal to that of the s2-length
if (i - j == n2)
break;
}
// release
while (j < i) {
f2 = true;
if (m1 == m2) {
cnt += 1;
arr.push_back(j + 1);
}
j++;
removeFromMap(m1, s1[j]);
// as soon as the window-size is becomes less than the s2-length
// stop releasing
if (i - j < n2)
break;
}
if (f1 == false && f2 == false)
break;
}
return cnt;
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cout
Very Nice Explanation.......Keep making videos
Thank you, I will
Sir ye bhi platform par nhi hai?
ok beta dalwata un
Looking smart sir
So nice of you
class Solution {
int search(String pat, String txt) {
HashMap pMap=new HashMap();
HashMap sMap=new HashMap();
for(int i=0;i
Anyone ever wonders......
if(hmap1.equals(hmap2)){
//code
}
This is a valid statement in java.
Leetcode AC Solution :
class Solution {
public boolean check(int a[], int b[]) {
for(int i = 0; i < 26; i ++) {
if(a[i] != b[i])
return false;
}
return true;
}
public List findAnagrams(String s, String p) {
int arr[] = new int[26];
List ans = new ArrayList();
for(int i = 0 ; i < p.length(); i ++)
arr[p.charAt(i) - 'a'] ++;
int start = 0, end = 0;
int ch[] = new int[26];
while(end < s.length()) {
ch[s.charAt(end) - 'a'] ++;
if(end < p.length()-1)
end ++;
else {
if(check(ch, arr))
ans.add(start);
ch[s.charAt(start) - 'a'] --;
start ++;
end ++;
}
}
return ans;
}
}
What will be the time complexity in this case?
For comparison part
O(n), n being the size of source string, comparison function runs in constant time as atmost 26 comparisons will be done as only these many alphabets are there.
more confusion ....... no use to explain in 20 mints
We are sorry to disappoint you. We will redo this video, we request you to watch this video again in a few days.
Complete Java Code:
class Solution {
private boolean compareMaps(HashMap sMap, HashMap pMap){
for(Map.Entry entry: pMap.entrySet()){
char key = entry.getKey();
int val = entry.getValue();
if(!sMap.containsKey(key) || sMap.get(key) != val){
return false;
}
}
return true;
}
public List findAnagrams(String s, String p) {
List result = new ArrayList();
if (s.length() < p.length()) {
return result; // No possible anagrams if the length of p is greater than the length of s
}
HashMap sMap = new HashMap();
HashMap pMap = new HashMap();
for(int i = 0; i < p.length(); i++){
sMap.put(s.charAt(i), sMap.getOrDefault(s.charAt(i), 0) + 1);
pMap.put(p.charAt(i), pMap.getOrDefault(p.charAt(i), 0) + 1);
}
int j = 0, i = p.length();
while (i < s.length()) {
int index = i - p.length();
if (compareMaps(sMap, pMap)) {
result.add(index);
}
char ch = s.charAt(i);
sMap.put(ch, sMap.getOrDefault(ch, 0) + 1);
char prevChar = s.charAt(index);
int val = sMap.get(prevChar);
if (val == 1) {
sMap.remove(prevChar);
} else {
sMap.put(prevChar, val - 1);
}
i++; // Increment i to move the sliding window
}
// Check if the last window is an anagram
if (compareMaps(sMap, pMap)) {
result.add(i - p.length());
}
return result;
}
}
WHATS WRONG WITH THIS ONE IF THE TEST CASE. (GEEKSFORGEEKS)
class Solution {
public boolean compare(HashMap pmap,HashMap smap){
for(char srcCh: smap.keySet()){
if(pmap.getOrDefault(srcCh,0)!=smap.get(srcCh)){
return false;
}
}
return true;
}
int search(String p, String s) {
HashMap smap = new HashMap();
HashMap pmap = new HashMap();
for(int i =0;i