Intuition

Another way to read the problem is: find if all s characters are present in t, in the same order. It doesn’t have to be consecutive. We need to keep two pointers:

• One for the string t
• One for the string s

We got loop through the string t, and if t[tPointer] == s[iPointer], we increase both. If t[tPointer] != s[iPointer], will increase just tPointer. At the end if iPointer==len(s) we reach end of s, we are good, return True This will be solved in time O(n) and space(1), since is one pass and we don’t use additional structures other than the pointers.

Approach

As described above.

However, I forgot to consider the edge cases, and these are the following:

• Both empty, return true
• Only t is empty, return false
• Only s is empty, return true

Complexity

• Time complexity: O(n) (one pass solution)

• Space complexity: O(1) (no additional structures, only pointers)

Code

class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """

        if len(t) == 0 and len(s) ==0:
            return True
        if len(t) == 0 and len(s) > 0:
            return False
        if len(t) > 0 and len(s) == 0:
            return True

        pointer = 0
        for i in range(len(t)):
            if t[i] == s[pointer]:
                pointer+=1
                if pointer >= len(s):
                    return True
        return False