Problem description

Given a string s and a string t, check if s is subsequence of t.

You may assume that there is only lower case English letters in both s and t. t is potentially a very long (length ~= 500,000) string, and s is a short string (<=100).

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).

Example 1: s = “abc”, t = “ahbgdc”

Return true.

Example 2: s = “axc”, t = “ahbgdc”

Return false.

Solution

1. Since we can not change order for subseuqnces, we can employ greedy linear scan from the head of string t for the current char in s. If we find it in t, we move to the next position in s and scan from the position next to the match position in t.
2. If for some char in s, we can not find it in t, we reach then end of t and output False
3. We do this iteratively, until reach the end of s. If we reach the end of s, we output True
4. Below are my Two Pointer implementation

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        '''
        greedy approach
        keep two pointers i and j, we search s[i] in t, if j reach the end of t, we output false, otherwise we found s[i] == t[k], then we increment i, and search for s[i + 1] in t start from k.
        We keep doing this continously until we reach the end of s. If we reach end of s, we output True.
        '''
        m = len(s)
        n = len(t)
        i = 0
        j = 0
        while i < m and j < n:
            c = s[i]
            if t[j] != s[i]:
                j += 1
            else:
                i += 1
                j += 1
        if i == m:
            return True
        if j == n:
            return False