💬 Discord
Sign In
NeetCode #5LC-392EasyArrays & Hashing
← Back to All Problems

#5 · #392 · Is Subsequence(判断子序列)

📌 Problem Statement & Constraints

Given two strings s and t, return true if s is a subsequence of t. A subsequence is formed by deleting some characters without changing the relative order of the rest. Constraints: 0 <= s.length <= 100, 0 <= t.length <= 10^4.

💡 Core Algorithmic Approaches

  1. A two-pointer scan is the natural solution: one pointer walks s, the other walks t.
  2. Advance the t pointer on every step. Advance the s pointer only when the characters match.
  3. If the s pointer reaches the end of s, every character was matched in order, so s is a subsequence.
  4. The s pointer is the loop condition, so the scan stops as soon as s is fully consumed -- an early exit that helps on long inputs.

💻 Benchmark Python3 Implementation

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0                              # pointer into s
        for ch in t:
            if i < len(s) and ch == s[i]:
                i += 1                     # matched one character of s
            if i == len(s):
                return True                # early exit
        return i == len(s)


# Follow-up for many queries: precompute next-occurrence tables
class Solution2:
    def isSubsequence(self, s: str, t: str) -> bool:
        from bisect import bisect_left
        from collections import defaultdict
        pos = defaultdict(list)
        for j, ch in enumerate(t):
            pos[ch].append(j)
        cur = 0
        for ch in s:
            lst = pos.get(ch)
            if not lst:
                return False
            k = bisect_left(lst, cur)      # earliest occurrence at or after cur
            if k == len(lst):
                return False
            cur = lst[k] + 1
        return True

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(|t|) for the two-pointer version: t is scanned once. The precomputation variant is O(|t|) build plus O(|s| log |t|) per query, which pays off when the same t is queried many times.
💾 Space Complexity
O(1) for the two-pointer version; O(|t|) for the position index in the variant.

⚠️ Interview Pitfalls & Follow-ups

  • Confusing subsequence with substring: a subsequence need not be contiguous, so "ace" is a subsequence of "abcde".
  • Scanning s in the outer loop: then t would be rescanned for each character of s, giving O(|s| * |t|).
  • Forgetting the empty-s case: an empty string is a subsequence of any string, and the loop returns i == len(s) == 0, which is True.
  • Using t.find(ch, i) in a loop: correct, but find restarts its scan each time; the linear two-pointer walk is cleaner and strictly O(|t|).