Is Subsequence

Patrick Leaton
Published: March 16, 2021, 1:22 a.m.
Problem Description

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

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

Follow up:
If there are lots of incoming S, say S1, S2, ... , Sk where k >= 1B, and you want to check one by one to see if T has its subsequence. In this scenario, how would you change your code?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

 

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 <= 10^4
  • Both strings consists only of lowercase characters.

 

Description taken from https://leetcode.com/problems/is-subsequence/.

Problem Solution

#O(N) Time, O(1) Space
class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        sub_pointer, string_pointer = 0, 0
        while sub_pointer < len(s) and string_pointer < len(t):
            if s[sub_pointer] == t[string_pointer]:
                sub_pointer += 1
            string_pointer += 1
        return sub_pointer == len(s)

Problem Explanation

We can solve this question by using two pointers, one for each string. 

We will set both pointers at the beginning of their respective strings and each time there is a match, we will move both pointers forward.  Otherwise, we will just move the pointer for the non-subsequence string.

The overall idea is that the subsequence pointer acts as a checklist for all of the character ingredients it needs to be a part of the non-subsequence string, and if the subsequence pointer reaches the end of its string, that means all of those ingredients were present in the right order.

Let's start by initializing both pointers to zero, the first index of both strings.

        sub_pointer, string_pointer = 0, 0

 

While both pointers are within the bounds of their string, we will check for a match in elements.

        while sub_pointer < len(s) and string_pointer < len(t):

 

If there is a match then we will move the subsequence pointer forward to check off its current character as present within the other string.

            if s[sub_pointer] == t[string_pointer]:
                sub_pointer += 1

 

We will move the string pointer forward at the end of each iteration regardless.

            string_pointer += 1

 

Once one of the pointers has gone past the length of its string, we will break from the loop.  When that happens we will check if the subsequence pointer is the length of its string. 

If it is, then we know there was a match in all the subsequence elements for the longer string.  Otherwise, there were characters required that were missing.

        return sub_pointer == len(s)