I was shocked by the tags of this problem. Then when I looked at it I found without using these fancy algorithms, there is a rather straight-forward solution with linear time complexity.

Maybe I'm wrong and I would appreciate it if someone can tell me how to reduce it into logN using DP or BS?

Below is my Java solution:

'''

public boolean isSubsequence(String s, String t) {

```
if (t.length() == 0 && s.length() == 0) return true;
if (t.length() == 0) return false;
if (s.length() == 0) return true;
int target_index = 0;
for (int i = 0; i < t.length(); i ++) {
if (s.charAt(target_index) == t.charAt(i)) {
if (target_index == s.length()-1) return true;
target_index ++;
}
}
return false;
}
```

'''