Is Subsequence?

Problem:

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

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

Output: true

Example 2:

Input: s = “axc”, t = “ahbgdc”

Output: false

Solution

This is an easy character matching problem that can be solved using two pointers.

We use the first pointer, sp to iterate through the string s.

We use the second pointer, tp to iterate through the string t.

def isSubsequence(s, t):
    sp = tp = 0

    while sp < len(s) and tp < len(t):
        if s[sp] == t[tp]:
            sp += 1
        tp += 1

    return sp == len(s)

When we exit the while loop, if sp is equal to the length of s, then we have successfully matched all the characters of s in t in the same order of their appearance in s.

Runtime: Runtime is $O(n)$, where $n$ is the length of the longer string. The space complexity is $O(1)$.

Back to Two Pointers Problems

---

anusha-murali.github.io