{ }DevToolsDaily
ToolsInterview Prep
New
CheatsheetsDirectoryMy spaceBlog
Ctrl + K
Ask AI

Is Subsequence – Solution & Complexity

Interview solutions
/
Is Subsequence

Solution Walkthrough

  1. Step 1: Understand What Subsequence Means

    • s is a subsequence of t if all characters of s appear in t in the same order.
    • Characters in t may be skipped, but characters in s cannot be reordered.
    • An empty s is always a subsequence.

  2. Step 2: Think About a Direct Scan

    • We do not need to generate all possible subsequences of t.
    • Instead, scan t from left to right and try to match the next needed character from s.
    • If every character from s is matched, return True.

  3. Step 3: Use Two Pointers

    • Pointer i tracks the next character needed from s.
    • Pointer j is the current position while scanning t.
    • When s[i] == t[j], advance i; always continue scanning through t.
    def is_subsequence(s, t):
    i = 0
    for char in t:
        if i < len(s) and s[i] == char:
            i += 1
    return i == len(s)

  4. Step 4: Handle Completion Early

    • Once i reaches len(s), every character in s has been matched.
    • At that point we can return True without scanning the rest of t.
    • If the scan ends first, return whether all of s was matched.
    def is_subsequence(s, t):
    i = 0
    for char in t:
        if i == len(s):
            return True
        if s[i] == char:
            i += 1
    return i == len(s)

  5. Step 5: Final Complete Solution

    • The scan preserves order because t is processed left to right exactly once.
    • Time complexity is O(len(t)) and space complexity is O(1).
    • The empty string case works naturally because i == len(s) at the start.
    def is_subsequence(s: str, t: str) -> bool:
    i = 0

    for char in t:
        if i == len(s):
            return True
        if s[i] == char:
            i += 1

    return i == len(s)
Learn the Two Pointers pattern: recognition cues, invariant, and ordered practice →

FAQ

See also

Practice Is Subsequence online (run code in the browser)Find the Index of the First Occurrence in a String solution (easy)Palindrome String solution (easy)3Sum solution (medium)3Sum Closest solution (medium)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsPricingContact Us © Monkey SkatesHave kids?