Is Subsequence | With Follow Up Solved | 2 Approaches | AMAZON | Leetcode - 392

Similar Problem (Follow Up) :

This is the 19th Video on our strings Playlist.
In this video we will try to solve a very good Problem - Is Subsequence (Leetcode-392).

I will explain the intuition so easily that you will never forget and start seeing this as cakewalk EASYYY.
We will do live coding after explanation and see if we are able to pass all the test cases.

Problem Name : Is Subsequence
Company Tags : AMAZON

╔═╦╗╔╦╗╔═╦═╦╦╦╦╗╔═╗
║╚╣║║║╚╣╚╣╔╣╔╣║╚╣═╣
╠╗║╚╝║║╠╗║╚╣║║║║║═╣
╚═╩══╩═╩═╩═╩╝╚╩═╩═╝

#coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge #leetcodequestions #leetcodechallenge #hindi #india #coding #helpajobseeker #easyrecipes #leetcode #leetcodequestionandanswers #leetcodesolution #leetcodedailychallenge#leetcodequestions #leetcodechallenge #hindi #india #hindiexplanation #hindiexplained #easyexplaination #interview#interviewtips #interviewpreparation #interview_ds_algo #hinglish #github #design #data #google #video #instagram #facebook

[avishkargaikwad]

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 😊😊

[FanIQQuiz]

"JAHANPANAH TUSSI GREAT HO, TOHFA KABOOL KARO" ❣❣❣❣

[codestorywithMIK]

🎆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) :
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<Character, List<Integer>> 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<Integer> 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;
}
}

[Shubham-ycnz]

I was so after watching this video finally clarified, prev was actually storing index of 't' string
Thanks <3

[wearevacationuncoverers]

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

[rohitrajput]

Never seen such a detailed explaination before.

[harahsaini]

Bhaiya Aapka padhaya hua bauth aache se samajh aa jata h, great ho aap

[dayashankarlakhotia]

class solution {
Public boolean is Subsequence(string s, string t){
int i=0, j=0;
while (i<s.length ()&&j<t.length()){
if(s.charAt (i)==t.charAt (j))i++;
j++;
}
return i==s.length ();
}
};
follow up questions approach. leetcode 792.
class solution {
Public int num Matching Sub Seq( string s, string []works){
Hash map <string, character >mpp=new Hash map <>();
for(string a:words){
mpp.put (a, get or Default (a, 0)+1);
}
int ans=0;
for(string a:mpp.key set()){
int i=0, j=0;
while (i<s.length ()&&j<a.length()){
if(s.charAt (i)==a.char At(j)){
i++;
j++:
}else {
i++;
}
}
if(j==a.length ())
ans+=mpp.get (a);
}
return ans;
}
};

[floatingpoint]

approach 2 was amazing thanks for showing us that

[yashdeshmukh]

class Solution {
public boolean isSubsequence(String s, String t) {
if (s==null || t==null) return false;

Map<Character, List<Integer>> map = new HashMap<>(); //<character, index>

//process 1
for(int i=0; i<t.length(); i++){
char curr = t.charAt(i);
if(!map.containsKey(curr)){
map.put(curr, new ArrayList<Integer>());
}
map.get(curr).add(i);
}
int prev = -1;
for(int i=0; i<s.length(); i++){
char c = s.charAt(i);
if(map.get(c) == null){
return false;
}else{
List<Integer> list = map.get(c);
prev = binaraySearch(prev, list, 0, list.size()-1);
if(prev==-1){
return false;
}
}
prev++;
}
return true;
}
public int binaraySearch(int index, List<Integer> list, int start, int end){
while(start<=end){
int mid = start+(end - start)/2;
if(list.get(mid)<index){
start = mid + 1;
} else {
end = mid - 1;
}
}
return start == list.size() ? -1 : list.get(start);
}
}
this is the followup java code
I dont get it why is the need in java code to update prev++ and not in C++...! but great explanation i will debug on my own and will update it.

[vinayjangra]

time complexity should be, O(t.length)

[dhairyachauhan]

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<=N<=1e4)
s.length() = M (0<=M<=100)
K(no. of strings to be processed)

Approach 1:
complexity o(N) given N can be at max 10000 hence o(10000) in the worst case.For one string
For K strings
O(KN)
Overall O(1e4*K)

Approach 2:
complexity O(MlogN){since logN time is taken for upperbound for the worst case string
eg: times)"
and M is the time we iterate over string S.

now for K such strings complexity = O(K*MlogN) Now K remains same for both cases
but MlogN = 100*log(1e4) ≈ 100*13= O(1300*k)
Overall O(1300*K)
which is far better.

[Tesla_Arc]

I have one doubt - how did you come up with this approach, what was your thought process ? could be please tell
Great Explanation Bro

[samarohochattopadhyay]

shouldn't the T.C for linear approach be O(Max(s, t)) ?

[saumilvachheta]

Hi, can you make videos in Java? If not, can you suggest resources/YouTubeChannels to learn DSA in Java?

[maheshvarandani]

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

[knoxmacroboy]

bhaiya can u please make a video on prefix sum approach i am lacking a behind the intuition still trying

[dayashankarlakhotia]

i wrote follow up question in Bf approach why not give Tle please explain?
😂❤