[Problem Solving] Is Subsequence – Two Pointer Technique

Given two strings s and t, check if s is a subsequence of t. A subsequence can be formed by deleting some characters in a string without changing the order of the other characters.

Input: s = “abc”, t = “ahbgdc“
Output: true

The simplest way to solve this problem is to use the two-pointer technique where we designate two different pointers to traverse s and t simultaneously. If the characters match, then we move on to check the next character of s against t, otherwise we move on to the next character in t. By the time we are done, there should be no characters left in s to be compared and therefore s must be a substring of t.

Time Complexity: The loop ends when we run out of characters to compare in either s or t. The worst case happens when we run through all the characters in t, so the time complexity is O(T).

Space Complexity: O(1)

Code:

def isSubsequence(self, s: str, t: str) -> bool:

    i, j = 0, 0

    while i < len(s) and j < len(t):
        
        if s[i] == t[j]:
            i += 1
            
        j += 1
    return i == len(s)

Testing:

For this problem, the following test cases will cover various situations.

• Empty s
• Empty t
• s string length greater than t
• A few other random test cases

I find all other approaches to be kind of an overkill, so I hope you enjoyed this simple approach. Have a great day!