Subsequence Checker

Problem

Given two strings s and t, return True if s is a subsequence of t.

A subsequence means every character of s appears in t in the same relative order — but not necessarily at consecutive positions. Characters in t that don’t belong to s can be freely skipped.

s = "ace",  t = "abcde"  →  True   (a at t[0], c at t[2], e at t[4] — order preserved)
s = "aec",  t = "abcde"  →  False  (e appears at t[4], but c appears at t[2] — order violated)
s = "",     t = "abc"    →  True   (empty string is always a subsequence of anything)
s = "abc",  t = ""       →  False  (non-empty s cannot match inside an empty t)

Intuition

Imagine t as a long river and s as a treasure map with a sequence of landmarks you need to visit in order. You paddle down the river from left to right — you can’t go back upstream. Each time you reach a landmark that matches the next one on your map, you check it off. If you check off every landmark before reaching the end of the river, the journey was valid.

That’s exactly the structure here. You have two positions to track:

• Where you are in t — always moving forward, skipping anything that doesn’t match
• How far you’ve matched in s — only advances when the current character of t matches the current target in s

This is a simultaneous traversal problem because you can’t answer the question by scanning s alone or t alone. You need to walk both at the same time: t’s pointer tells you “what character of t am I looking at right now?” and s’s pointer tells you “which character of s am I currently trying to match?”

If s’s pointer reaches the end of s, all characters were matched in order — return True. If t’s pointer reaches the end of t first, s still has unmatched characters — return False.

Key Observations

1. t’s pointer always advances. You scan every character of t exactly once, whether or not it matches.
2. s’s pointer only advances on a match. This enforces the ordering constraint: you can only check off a character once you actually find it at or after the current position in t.
3. No backtracking. Once you move past a position in t, you never revisit it. This is what gives the O(N + M) time complexity.
4. Order matters, gaps don’t. s = "ace" succeeds even though positions 1 and 3 (b and d) are skipped. But s = "aec" fails because e cannot appear before c in the subsequence.

Approach

---
config:
  theme: base
  themeVariables:
    primaryColor: "#dbeafe"
    primaryBorderColor: "#3b82f6"
    primaryTextColor: "#1e3a5f"
    lineColor: "#64748b"
    secondaryColor: "#ede9fe"
    tertiaryColor: "#fef9c3"
---
flowchart TB
  Start(["index1 = 0, index2 = 0"])
  Check{"index1 < len(s)<br/>AND index2 < len(t)?"}
  Match{"s[index1] == t[index2]?"}
  AdvBoth["index1 += 1<br/>index2 += 1"]
  AdvTwo["index2 += 1"]
  Done{"index1 == len(s)?"}
  RetTrue(["return True"])
  RetFalse(["return False"])

  Start --> Check
  Check -->|"yes"| Match
  Check -->|"no"| Done
  Match -->|"yes — found target char"| AdvBoth --> Check
  Match -->|"no — skip t[index2]"| AdvTwo --> Check
  Done -->|"yes — all of s matched"| RetTrue
  Done -->|"no — t ran out first"| RetFalse

Simultaneous traversal — index2 advances every step; index1 only advances when a match is found. The loop exits when either string is exhausted.

Step-by-step logic:

1. Start both pointers at position 0.
2. Each iteration: if s[index1] == t[index2], the current target character in s was found — advance both pointers.
3. If no match, t[index2] is not the character we need right now — advance only index2 to check the next character in t.
4. When the loop exits (one of the strings is exhausted), check if index1 == len(s). If yes, every character in s was matched in order — True. Otherwise, s still has unmatched characters — False.

Solution

class Solution:
    def is_subsequence(self, s: str, t: str) -> bool:
        # Points at the next character in s we need to find inside t
        index1 = 0
        # Points at the current character in t we are examining
        index2 = 0

        # Run while both strings still have unexamined characters
        while index1 < len(s) and index2 < len(t):
            if s[index1] == t[index2]:
                # Found the current target — advance s's pointer to the next target
                index1 += 1
            # Always advance t's pointer: we examine every character of t exactly once
            index2 += 1

        # If index1 reached the end of s, every character was matched in order
        # If index1 < len(s), t ran out before all of s was matched
        return index1 == len(s)


sol = Solution()
print(sol.is_subsequence("ace", "abcde"))  # True
print(sol.is_subsequence("aec", "abcde"))  # False
print(sol.is_subsequence("", "abc"))       # True  — empty is always a subsequence
print(sol.is_subsequence("abc", ""))       # False — non-empty s can't fit in empty t
print(sol.is_subsequence("abc", "abc"))    # True  — s equals t, still a valid subsequence

Trace

index1 = 0,  index2 = 0

Step 1 │ index1=0 ('a'), index2=0 ('a') │ 'a'=='a' match   │ index1=1, index2=1
Step 2 │ index1=1 ('c'), index2=1 ('b') │ 'c'≠'b' no match │ index1=1, index2=2
Step 3 │ index1=1 ('c'), index2=2 ('c') │ 'c'=='c' match   │ index1=2, index2=3
Step 4 │ index1=2 ('e'), index2=3 ('d') │ 'e'≠'d' no match │ index1=2, index2=4
Step 5 │ index1=2 ('e'), index2=4 ('e') │ 'e'=='e' match   │ index1=3, index2=5
Loop exits: index1=3 == len(s)=3

Return: True ✓

Note: index2 advanced on every step; index1 only advanced on steps 1, 3, and 5.
The three skipped characters ('b', 'd') in t were irrelevant to the match.

index1 = 0,  index2 = 0

Step 1 │ index1=0 ('a'), index2=0 ('a') │ match   │ index1=1, index2=1
Step 2 │ index1=1 ('e'), index2=1 ('b') │ no match│ index1=1, index2=2
Step 3 │ index1=1 ('e'), index2=2 ('c') │ no match│ index1=1, index2=3
Step 4 │ index1=1 ('e'), index2=3 ('d') │ no match│ index1=1, index2=4
Step 5 │ index1=1 ('e'), index2=4 ('e') │ match   │ index1=2, index2=5
Loop exits: index2=5 == len(t)=5

Return: index1 == len(s) → 2 == 3 → False ✓

Note: 'e' was found successfully, but now index2 has run off the end of t.
s[2]='c' was never matched — and it can't be, because 'c' in t was already
passed at index2=2, before 'e' was found. The ordering is violated.

Complexity

Time: In the worst case (no match, or a match only at the very end), index2 scans all of t (M steps) and index1 scans all of s (N steps). Total steps: at most N + M.

Space: Only two integer pointers — no auxiliary data structures needed.

Edge Cases

Key Takeaway

Use simultaneous traversal when one string’s pointer always advances and the other only advances on a match — the answer is whether the conditional pointer exhausts its sequence first. Remember: index2 (for t) is the engine that drives the loop; index1 (for s) is the progress meter.