{ }DevToolsDaily
ToolsInterview
Problems
New
CheatsheetsChat
New
BlogPricing
Ctrl + K

Is Subsequence – Solution & Complexity

Interview solutions
/
Is Subsequence

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. 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. 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. 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. 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)

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)Container With Most Water solution (medium)Count Vowels solution (easy)All coding interview problems
Buy me a coffeePrivacyTermsFAQChangelogFeature RequestsBlogAll ToolsContact Us © Monkey SkatesHave kids?