Leetcode 392 - Is Subsequence

Problem

Leetcode 392 - Is Subsequence

Example:

s = "abc", t = "ahbgdc"
Return true.

s = "acb", t = "ahbgdc"
Return false.

s = "axc", t = "ahbgdc"
Return false.

Approach

Since we’re checking if s is a subsequence of t, and subsequence means that the characters in s appear in t in the same order, we can use two pointers to check if s is subsequence of t. We also have to keep in mind that s can be empty string, and length of s can be longer than t. Therefore, we need to check if length of s is empty, we return true, and if length of s is greater than length of t, we return false.

Visual representation of the approach:

s = "abc", t = "ahbgdc"
counter = 0 // index of s
index = 0 // index of t

s[counter] = a,  t = "ahbgdc"
                      ^
Since s[counter] == t[index], we increment both counter and index.

s[counter] = b,  t = "ahbgdc"
                       ^
Since s[counter] != t[index], we increment index.

s[counter] = b,  t = "ahbgdc"
                        ^
Since s[counter] == t[index], we increment both counter and index.

s[counter] = c,  t = "ahbgdc"
                         ^
Since s[counter] != t[index], we increment index.

s[counter] = c,  t = "ahbgdc"
                          ^
Since s[counter] != t[index], we increment index.

s[counter] = c,  t = "ahbgdc"
                           ^
Since counter == len(s), we return true.    

Here’s the code implementation of the approach:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # if s is empty, return true
        if len(s) == 0:
            return True
        # if length of s is greater than length of t, return false
        if len(s) > len(t):
            return False

        # initialize counter for s
        counter = 0
        # iterate through t
        for c in t:
            if s[counter] == c:
                counter += 1
                if counter == len(s):
                return True
        return False

Time Complexity and Space Complexity

Since we’re iterating through t once, the time complexity is $ O(n) $ where $ n $ is the length of $ t $.

Since we’re not using any additional space, the space complexity is $ O(1) $.