Teaching Kids Programming – Is Subsequence Algorithm via Two Pointer

Teaching Kids Programming: Videos on Data Structures and Algorithms

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

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

Constraints:
0 <= s.length <= 100
0 <= t.length <= 104
s and t consist only of lowercase English letters.

Follow up: If there are lots of incoming s, say s1, s2, …, sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Is Subsequence Algorithm via Two Pointer

Let’s have two pointers: compare the string (to check if subsequence) and the target string, move the first pointer if it matches the second pointer. Move second pointer at each iteration until it reaches the end. The algorithm can also be used on the list.

If the first string is longer than the second string, it is impossible for the first string to be a subsequence of the second one.

1
2
3
4
5
6
7
8
9
10
11

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        ls, lt = len(s), len(t)
        if ls > lt:
            return False
        i = j = 0
        while i < ls and j < lt:
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == ls

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        ls, lt = len(s), len(t)
        if ls > lt:
            return False
        i = j = 0
        while i < ls and j < lt:
            if s[i] == t[j]:
                i += 1
            j += 1
        return i == ls

The time complexity is O(N) where N is the number of the characters in the target string/list.

String Subsequence Algorithms:

• Teaching Kids Programming – Is Subsequence Algorithm via Recursion (Greedy)
• Teaching Kids Programming – Is Subsequence Algorithm via Two Pointer
• The Subsequence Algorithm for Two Strings – How to Check if a String is Subsequence of Another?
• GoLang Function of Checking Is Subsequence
• Algorithms to Check if a String is a Subsequence String of Another String
• in Python, you can do this in Pythonic way: Python Function to Check Subsequence

–EOF (The Ultimate Computing & Technology Blog) —