Is Subsequence | Leetcode #392 | Binary search + Map | 2 Pointer

This video explains a very important programming interview problem which is to find if a given string is a subsequence of another string or not.This problem is a variant of LCS (longest common subsequence) but solving it using LCS is very inefficient.A very simple and intuitive way to solve it is by using 2 pointer approach.But what happens if we face a lot of queries! Let's say queries comes in order of billions. Then how to solve this efficiently? I have shown second approach which solves this follow up problem for large queries efficiently.I have explained the code walkthrough at the end of the video.CODE LINK is present below as usual. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)

=================================================================
=================================================================

OTHER PROBLEMs:-

[techdoseu]

Time complexity for Approach-2 using map + binary search can be simplified to: O(T+SlogT).

[jaden]

The follow up is what I'm looking for

[nishpawar]

How can i access vector elements inside unordered map for binary search .(cpp)

[tejaswigutta]

1)How is the TC for first method is o(s+t) ? We are looping only for length of string t times right?
2)how's the TC for second method is o(tlogt) ? We are inserting all the characters of string t into hashmap which is o(t) and for every character in S we are doing binary search whose worst case tc is (s*logt). So on a whole it's o(t+slogt) right?

JUST ASKING :) @TECH DOSE

[fatimajaffal]

class Solution {
public:
bool isSubsequence(string s, string t) {
int start = 0;
for(int i=0;i<t.size();i++) {

if(s[start] == t[i]) start++;

}

return start == s.size();

}
};

[Println]

for (int i = 0; i < n && j < m; i++)
if (mainString[j] == keyString[i])
j++;


return (j == m); // if found true else false

[manideepgupta]

bool fun(string a, string b){
int count=0;
for(int i=0, j=0;j<b.length();j++){
if(a[i]==b[j]){
i++;
count++;
}
}
if(count==a.length())
return true;
else
return false;
}
//thise will take just o(length(t)) time

[md_aaqil]

Java Solution
class Solution {
public boolean isSubsequence(String s, String t) {
int i=0;
int j=0;
while(i<s.length() && j<t.length())
{
if(s.charAt(i)==t.charAt(j))
i++;
j++;
}
return i==s.length();
}
}

[KamleshSharma-sirq]

```python
def isSubsequence(self, s, t):
s=list(s)
p=len(t)-len(s)
for i in range(p):
s.append('')

t=list(t)

j=0

i=0

while(i<len(s) and j<len(t)):

if(s[i]==t[j]):
s[i]=''
i+=1
j+=1
else:

j+=1

x=s.count('')

if(x==len(s)):
return True
else:
return False

```Hi sir is it two pointer approach, i solved the problem but i don't know in what category this solution comes under whether it is Two pointer and By the way your explaination is always awesome...

[SahilThakur]

FYI by performing calculations on the leetcode constraints for problem 792:

s = abacdaec len - m
t = ace len - n

k = number of t

Approach 1
O(k*(m+n)) = 5000*(5*10^4+50) = 250250000

Approach 2
O(k*n*(logm)) = 5000*50*log(5*10^4) = 1174742.50108

Approach2 < Approach1 in terms of time complexity

In my POV above will always be true if there is a single query or multiple.

[manthankhorwal]

I dont think 1st method has time complexity what you said it is O(t) because while using pointers if character match you move both pointers and if they not, then you move t string pointer... So in both cases you are moving pointer of t string....But for query, 2 method is good

[Yash-ukib]

sir map adds logarithmic time as well!! haven't u considered that??

[yitingg]

Good evening !!! Thank you so much Surya for putting the time to explain the time complexity. It is far more important than just showing the code lol. The time complexity analysis is a little hard for me to digest 😭😭 I do understand O(T+SlogT) though, but in the video I think you said it takes T Log T to build the map and then S Log S to find each answer which I am scratching my head to understand why.

[md_aaqil]

Java Solution
Time-O(n*log(n))
class Solution {
public boolean isSubsequence(String s, String t) {
ArrayList<Integer> adj[]=new ArrayList[26];
for(int i=0;i<26;i++)
{
adj[i]=new ArrayList();
}
for(int i=0;i<t.length();i++)
{
adj[t.charAt(i)-'a'].add(i);
}
int last[]=new int[26];
int curr=-1;
for(int i=0;i<s.length();i++)
{
int
int pos=s.charAt(i)-'a';
last[pos]=findlast(adj[pos], last[pos], curr);//upper bound implementation in java
if(last[pos]==-1)
return false;
curr=adj[pos].get(last[pos]);

}
return true;
}
public int findlast(ArrayList<Integer> arr, int s, int key)
{
int e=arr.size()-1;
if(arr.size()==0 || arr.get(arr.size()-1)<=key)
return -1;
while(s<e)
{
int mid=s+(e-s)/2;
if(arr.get(mid)<=key)
s=mid+1;
else
e=mid;

}
return e;
}

}

[AmazingWorld-fwoc]

The time complexity should be Len(s)*log(t) ?
Because we will traverse every elements of string s and then use binary search to find desired index in the map and that'll take log(t) .

So it should be Len(s)*log(t)

[tanishqgupta]

After your doesn't need to go any video 🙂🙂🙏🙏

[rohithkumartangudu]

I used regular expression and got time limit exceeded error for few cases. I did not understand y it got.
The way I used regular expression is (java) for string t let take t is acb then I made that as
. *a.*c.*b. * and then I searched for this regular expression in the string s

[tonyshin]

Thanks for another excellent video. I have always been enjoying your insights. Here is one issue to address. It is the time complexity of the first approach (two pointers). As some people already mentioned, I also agree that the time complexity is O(T), not O(S + T), where S is the length of string s and T is the length of string t.
Here is what I think:
When we say that the time complexity is O(S + T), it means O(max(S, T)). O(max(S, T)) means that when S > T, it is O(S), and when T > S, it is O(T).
However, when S > T, the algorithm stops when the second index 'tpos' reaches the end of the string t before the first index 'i' reaches the end of the string s. Therefore, I believe the time complexity is O(T), not O(S + T).

[ashwanikumar]

Great video. Thank you for including the follow-up question. The explanation is great.

[agileprogramming]

I didn't understand why the complexity of making the map was O(tlog(t))