We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Is Subsequence

Difficulty: Easy

Problem Description

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.

Key Insights

  • A subsequence maintains the order of characters but may skip characters.
  • We can use a two-pointer technique to efficiently check for subsequence.
  • If we can traverse all characters in s while matching them in t, then s is a subsequence of t.

Space and Time Complexity

Time Complexity: O(n), where n is the length of string t.
Space Complexity: O(1), as we are using a constant amount of space.

Solution

To determine if string s is a subsequence of string t, we can employ the two-pointer technique. We'll maintain two pointers: one for string s and one for string t. We will iterate through t and try to match each character of s sequentially. If we find a match, we move the pointer for s forward. If we reach the end of s, it means all characters have been matched in order, and we return true. If we finish iterating through t without matching all characters of s, we return false.

Code Solutions

def isSubsequence(s: str, t: str) -> bool:
    s_pointer, t_pointer = 0, 0
    
    # Iterate through t
    while t_pointer < len(t):
        # If characters match, move the s pointer
        if s_pointer < len(s) and s[s_pointer] == t[t_pointer]:
            s_pointer += 1
        # Always move the t pointer
        t_pointer += 1
    
    # If we have matched all characters of s
    return s_pointer == len(s)
← Back to All Questions