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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Is Subsequence

Number: 392

Difficulty: Easy

Paid? No

Companies: Meta, Google, Amazon, Yandex, Microsoft, Pinterest, Tekion, Bloomberg, Salesforce, Adobe, Yahoo, Apple, TikTok, Accenture, Nvidia, Tinkoff, Wix

Problem Description

Given two strings s and t, determine whether s is a subsequence of t. A subsequence is formed by deleting zero or more characters from t without changing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde" but "aec" is not.

Key Insights

  • Use a two-pointer approach: one pointer traversing s and one traversing t.
  • As you iterate through t, if the current character matches the current character in s, move the pointer in s.
  • If the pointer in s reaches the end, all characters were matched in order, so s is a subsequence of t.
  • In the follow-up scenario with many s strings and one t, preprocess t by mapping each character to its indices, enabling binary search for the next occurence in t for each character of s.

Space and Time Complexity

Time Complexity: O(n + m), where n is the length of t and m is the length of s. Space Complexity: O(1) for the simple two-pointer approach. The preprocessing method (follow-up) requires extra space for the mapping, i.e., O(n).

Solution

We use a two-pointer technique to solve the problem. One pointer goes through the string s while the other goes through t. Every time a matching character is found, move the pointer in s. If by the end of t the pointer in s has reached the end, then s is a subsequence of t. For the follow-up scenario with many s queries, pre-process t by creating a mapping from each character to a list of its positions in t. Then for each s, use binary search to quickly find a valid next position for each character.

Code Solutions

# Python solution with two pointers

def isSubsequence(s, t):
    # Initialize pointer for s
    s_index = 0
    # Iterate over each character in t
    for char in t:
        # If the pointer hasn't reached the end of s and the character matches
        if s_index < len(s) and s[s_index] == char:
            s_index += 1  # move pointer in s to next character
        # If all characters in s are found, return True
        if s_index == len(s):
            return True
    # Return whether the pointer reached the end of s after traversing t
    return s_index == len(s)

# Example usage:
print(isSubsequence("abc", "ahbgdc"))  # Output: True
print(isSubsequence("axc", "ahbgdc"))  # Output: False
← Back to All Questions