In my opinion this man going to change the entire community of Data Structure And Algorithm... Another next level video Looking for your contest solution video 😊😊
🎆Small Correction : Time Complexity of First Approach will be O(max(m, n)) because our for loop will not run more than max(m, n). Similar Problem (Follow Up) : Leetcode-792 - leetcode.com/problems/number-of-matching-subsequences/ My Code for Leetcode-792 - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/Binary%20Search/Number%20of%20Matching%20Subsequences.cpp C++ & JAVA Code present in my Github link in the Description /*************************** JAVA ******************************/ //Follow Up Approach //Approach-1 (Using Binary Search) -> This is an important concept for qns like Leetcode-792 public class Solution { public boolean isSubsequence(String s, String t) { Map mp = new HashMap(); for (int i = 0; i < t.length(); i++) { char ch = t.charAt(i); mp.computeIfAbsent(ch, k -> new ArrayList()).add(i); } int prev = -1; for (char ch : s.toCharArray()) { if (!mp.containsKey(ch)) return false; List indices = mp.get(ch); int index = Collections.binarySearch(indices, prev + 1); if (index < 0) index = -index - 1; if (index == indices.size()) return false; prev = indices.get(index); } return true; } } //Approach-2 (Simplest O(n) approach) public class Solution { public boolean isSubsequence(String s, String t) { int m = t.length(); int n = s.length(); int i = 0, j = 0; while (i < m && j < n) { if (t.charAt(i) == s.charAt(j)) { j++; } i++; } return j == n; } }
I knew this guy will also cover followup Qn. This channel is no doubt the MOST UNDERRATED channel I have ever encountered. Thanks a lot for the detailed explanation
Hi there, I usually always add JAVA code exactly similar to my C++ version. You can find them in the same Github link in the description. I have updated. /************************* JAVA *******************************/ //Follow Up Approach //Approach-1 (Using Binary Search) -> This is an important concept for qns like Leetcode-792 public class Solution { public boolean isSubsequence(String s, String t) { Map mp = new HashMap(); for (int i = 0; i < t.length(); i++) { char ch = t.charAt(i); mp.computeIfAbsent(ch, k -> new ArrayList()).add(i); } int prev = -1; for (char ch : s.toCharArray()) { if (!mp.containsKey(ch)) return false; List indices = mp.get(ch); int index = Collections.binarySearch(indices, prev + 1); if (index < 0) index = -index - 1; if (index == indices.size()) return false; prev = indices.get(index); } return true; } } //Approach-2 (Simplest O(n) approach) public class Solution { public boolean isSubsequence(String s, String t) { int m = t.length(); int n = s.length(); int i = 0, j = 0; while (i < m && j < n) { if (t.charAt(i) == s.charAt(j)) { j++; } i++; } return j == n; } }
@@codestorywithMIK hi, thanks for your response. Actually I didn't open the GitHub link. My bad. Your videos are good, helps to understand logic. Thanks.
In my opinion this man going to change the entire community of Data Structure And Algorithm...
Another next level video
Looking for your contest solution video 😊😊
True 💯
Means a lot to me ❤️❤️🙏🙏
"JAHANPANAH TUSSI GREAT HO, TOHFA KABOOL KARO" ❣❣❣❣
Khao Maa Kasam😂
@@ashutosh61290 🤣
Thank you sir 😊
🎆Small Correction : Time Complexity of First Approach will be O(max(m, n)) because our for loop will not run more than max(m, n).
Similar Problem (Follow Up) :
Leetcode-792 - leetcode.com/problems/number-of-matching-subsequences/
My Code for Leetcode-792 - github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Arrays/Binary%20Search/Number%20of%20Matching%20Subsequences.cpp
C++ & JAVA Code present in my Github link in the Description
/*************************** JAVA ******************************/
//Follow Up Approach
//Approach-1 (Using Binary Search) -> This is an important concept for qns like Leetcode-792
public class Solution {
public boolean isSubsequence(String s, String t) {
Map mp = new HashMap();
for (int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
mp.computeIfAbsent(ch, k -> new ArrayList()).add(i);
}
int prev = -1;
for (char ch : s.toCharArray()) {
if (!mp.containsKey(ch))
return false;
List indices = mp.get(ch);
int index = Collections.binarySearch(indices, prev + 1);
if (index < 0)
index = -index - 1;
if (index == indices.size())
return false;
prev = indices.get(index);
}
return true;
}
}
//Approach-2 (Simplest O(n) approach)
public class Solution {
public boolean isSubsequence(String s, String t) {
int m = t.length();
int n = s.length();
int i = 0, j = 0;
while (i < m && j < n) {
if (t.charAt(i) == s.charAt(j)) {
j++;
}
i++;
}
return j == n;
}
}
Thanks a lot
I think, first me time complexity O(t.length) hi hongi...kyu ki s ki length matter nhi karti loop t.length time hi run hoga. So it's O(n)
I was so confused...... after watching this video finally clarified, prev was actually storing index of 't' string
Thanks
I’m glad it helped! ❤️
I knew this guy will also cover followup Qn. This channel is no doubt the MOST UNDERRATED channel I have ever encountered.
Thanks a lot for the detailed explanation
Never seen such a detailed explaination before.
2nd Approach was awesome 🔥
Indeed 😇
Mind blowing 🔥🔥🔥
The best explanation 🙌🔥
wow 🙌
The follow up was just lit🔥🔥
next level ❤
Excellent explaination🙂🙂🙂
This guy is a living legend
Your channel is gem
Bhaiya Aapka padhaya hua bauth aache se samajh aa jata h , great ho aap
Means a lot 🙏😇
Hats off 🔥
class solution {
Public boolean is Subsequence(string s,string t){
int i=0,j=0;
while (i
approach 2 was amazing thanks for showing us that
Thank you for watching 😇
class Solution {
public boolean isSubsequence(String s, String t) {
if (s==null || t==null) return false;
Map map = new HashMap(); //
//process 1
for(int i=0; i
Thank you for sharing ❤️🙏
time complexity should be, O(t.length)
I have one doubt - how did you come up with this approach, what was your thought process ? could be please tell
Great Explanation Bro
THANK YOU BHAIYA FOR SUCH WONDERFUL EXPLAINATION: JUST ONE THING TO BE ADDED
WHY THE MAP SOLUTION IS BETTER FOR LONGER RUN :-
LET,
t.length() = N (0
wow. thanks
Ak number.....
Thank you 😇
shouldn't the T.C for linear approach be O(Max(s,t)) ?
Yes yes, correct. I will add the correction in the caption.
Thanks a lot 😇🙏
O(min(s,t))
❤❤❤❤❤
Hi, can you make videos in Java? If not, can you suggest resources/UA-camChannels to learn DSA in Java?
ua-cam.com/video/CVA85JuJEn0/v-deo.htmlsi=Drq_QwonMCf23LYD
Hi there,
I usually always add JAVA code exactly similar to my C++ version.
You can find them in the same Github link in the description. I have updated.
/************************* JAVA *******************************/
//Follow Up Approach
//Approach-1 (Using Binary Search) -> This is an important concept for qns like Leetcode-792
public class Solution {
public boolean isSubsequence(String s, String t) {
Map mp = new HashMap();
for (int i = 0; i < t.length(); i++) {
char ch = t.charAt(i);
mp.computeIfAbsent(ch, k -> new ArrayList()).add(i);
}
int prev = -1;
for (char ch : s.toCharArray()) {
if (!mp.containsKey(ch))
return false;
List indices = mp.get(ch);
int index = Collections.binarySearch(indices, prev + 1);
if (index < 0)
index = -index - 1;
if (index == indices.size())
return false;
prev = indices.get(index);
}
return true;
}
}
//Approach-2 (Simplest O(n) approach)
public class Solution {
public boolean isSubsequence(String s, String t) {
int m = t.length();
int n = s.length();
int i = 0, j = 0;
while (i < m && j < n) {
if (t.charAt(i) == s.charAt(j)) {
j++;
}
i++;
}
return j == n;
}
}
@@codestorywithMIK hi, thanks for your response. Actually I didn't open the GitHub link. My bad. Your videos are good, helps to understand logic. Thanks.
How long it will take to develop a intuition to approach the question like you. I am solving questions since a year still lacking intuition
I also dream of becoming one day like this legend.
With hard work and consistency we can definitely become better and better
❤❤
bhaiya can u please make a video on prefix sum approach i am lacking a behind the intuition still trying
prefix sum for this problem ?
i wrote follow up question in Bf approach why not give Tle please explain?
😂❤
Sir aap kya karte ho .?
Yo