Is Subsequence Solution

Problem

Given two strings s and t, determine whether s is a subsequence of t. A subsequence means you can delete any characters from t (without reordering the rest) to produce s exactly.

Input: s = "ace", t = "abcde"
Output: true
Explanation: 'a', 'c', and 'e' appear in that order inside "abcde"

Counter-example: s = "aec", t = "abcde" → false, because 'e' comes after 'c' in t, but s needs 'e' before 'c'.

Intuition

Walk through t one character at a time and keep a finger on where you are in s. Every time the current character of t matches where your finger points in s, advance the finger. If the finger reaches the end of s, every character was found in order.

Solution — Two Pointers

Use one pointer into s that only moves forward when a match is found. Scan all of t; afterwards check whether the pointer reached the end of s.

Initialize s_idx = 0 to track how far through s we've matched.
Loop over every character in t.
When the current character equals s[s_idx], increment s_idx.
Stop early (implicit) if s_idx already equals len(s) — no further work needed.
After the loop, return s_idx == len(s).

1class Solution:
2    def isSubsequence(self, s: str, t: str) -> bool:
3        s_idx = 0  # how many characters of s we have matched so far
4
5        for char in t:
6            if s_idx < len(s) and char == s[s_idx]:
7                s_idx += 1  # only advance when s's next required character matches
8
9        return s_idx == len(s)

Time: O(|t|) — we scan t exactly once regardless of s.

Space: O(1) — only a single integer pointer beyond the inputs.

Complexity Summary

Approach	Time	Space	When to use
Two Pointers	O(\|t\|)	O(1)	Always — this is the natural linear scan

Common Mistakes

Checking character frequencies instead of order — verifying that s and t share the same characters by count ignores the required left-to-right ordering; "aec" has all the right characters but is not a subsequence of "abcde".
Advancing s_idx even when s_idx >= len(s) — the guard s_idx < len(s) is essential; without it you'll go out of bounds if extra matching characters appear in t after s is fully consumed.
Forgetting that empty s is always a valid subsequence — the algorithm handles this correctly (the loop runs but s_idx never increments since the condition s_idx < len(s) is immediately false; 0 == 0 returns true).
Returning after the first mismatch — you must keep scanning t, not bail out on a non-match; the subsequence might resume matching further along.
Using string find or indexOf — these locate the first occurrence, not a relative-order subsequence; t.find(s) looks for s as a contiguous substring, not a scattered one.

Is Subsequence — Solution

Problem

Intuition

Solution — Two Pointers

Complexity Summary

Common Mistakes

Related Problems

Ready to practice? Try it on SkillFlow