link to leetcode problem definition

Given a string s and a string t, check if s is subsequence of t. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ace" is a subsequence of "abcde" while "aec" is not).

Follow up: If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false

This problem comes down to a recursive solution with a greedy idea behind. We need to compare all characters of S with characters of T and if there is a match cross that as a result for the occurrence of the first character and move on. Our base case would be when all characters of S have been matched up and no more left, essentially when S is empty.

1. S has no characters -> return true
2. T has no characters (but S has) -> return false, meaning we exhausted T but still have some characters in S to match up
3. Iterate over T and compare characters of T to first of S

class Solution {
    public boolean isSubsequence(String s, String t) {
        var sLen = s.length();
        var tLen = t.length();
        if(sLen == 0) {
            return true;
        }
        for(int i = 0; i < tLen; i++) {
            if(s.charAt(0) == t.charAt(i)) {
                return isSubsequence(s.substring(1, sLen), t.substring(i + 1, tLen));
            }
        }
        
        return false;
    }
}