Domain 1EasyCORE

Is Subsequence

The problem asks us to determine if string `s` is a subsequence of string `t`. A subsequence means that all characters of `s` appear in `t` in the same order, but not necessarily consecutively. The inputs are two strings, `s` and `t`, and the output should be a boolean indicating whether `s` is a subsequence of `t`.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Binary Search#Dynamic Programming#Greedy

392. Is Subsequence

Model: qwen2.5-coder:14b
Topics: Binary Search,Dynamic Programming,Greedy
FAANG asked: 0
Acceptance rate: 49.6%


Problem Breakdown

The problem asks us to determine if string s is a subsequence of string t. A subsequence means that all characters of s appear in t in the same order, but not necessarily consecutively. The inputs are two strings, s and t, and the output should be a boolean indicating whether s is a subsequence of t.

Inputs:

  • s: A string that we want to check if it’s a subsequence.
  • t: A string in which we want to find the subsequence.

Outputs:

  • A boolean value (true or false) indicating whether s is a subsequence of t.

Implicit Constraints and Edge Cases:

  • If s is an empty string, it is trivially a subsequence of any string t.
  • If t is an empty string and s is not, then s cannot be a subsequence.
  • Both strings consist only of lowercase English letters.

Intuition

A brute-force approach would involve checking every possible substring of t to see if it matches s, which would be inefficient with high time complexity. Instead, we can use a two-pointer technique to traverse both strings simultaneously. This approach leverages the fact that we don’t need to find all subsequences but only check if one specific string is a subsequence.

The key insight is that we can iterate through t and try to match each character of s in order. If we can successfully match all characters of s while traversing t, then s is a subsequence of t.

Approach

We’ll use two pointers, one for each string:

  1. Initialize a pointer i for string s starting at 0.
  2. Iterate through each character in string t using another pointer j.
  3. If the current character in t matches the current character in s, move the pointer i to the next character in s.
  4. Continue this process until either all characters of s are matched (i reaches the end of s) or we finish traversing t.
  5. If i has reached the end of s, then s is a subsequence of t; otherwise, it is not.

Complexity Analysis

  • Time Complexity: O(n), where n is the length of string t. We traverse t once.
  • Space Complexity: O(1). We use only a constant amount of extra space for the pointers.

Solution

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

Edge Cases Handled

  • Empty s: If s is empty, the function returns true because an empty string is a subsequence of any string.
  • Empty t: If t is empty and s is not, the function returns false because a non-empty string cannot be a subsequence of an empty string.
  • No matching characters: If no characters in s match the order in t, the function correctly returns false.
  • All characters match: If all characters in s are found in t in order, the function returns true.

This solution is efficient and straightforward, making it suitable for both small and large inputs.

Follow-up

If there are lots of incoming strings s1, s2, ..., sk where k >= 10^9, and you want to check one by one to see if t has its subsequence, we can preprocess string t to make the checks more efficient. One approach is to use binary search on a list of indices for each character in t. This preprocessing step would take O(n) time where n is the length of t, and each subsequent check for an s would take O(m log n) time, where m is the length of s. This way, we can handle a large number of queries efficiently.