Is Subsequence (LeetCode 392)
You get two strings, s and t. Decide whether s is a subsequence of t: whether every character of s appears somewhere in t, in the same relative order, though not necessarily next to each other. Return true or false.
Worked Examples
s = "abc", t = "ahbgdc"truea, b and c appear in t at positions 0, 2 and 5, in that order.s = "axc", t = "ahbgdc"falset has no x at all, so s cannot be picked out of it.⚖️Formal Constraints & Bounds
0 <= s.length <= 1000 <= t.length <= 104sandtconsist only of lowercase English letters.
Core Insight
Walking t once and claiming the next unclaimed character of s the moment it is seen always finds a match if one exists, because the earliest available match for any character of s never costs a later character of s its own match.
Real-World Scenario & Production Applications
Checking whether a sequence of required approvals (s) all happened, in order, somewhere inside a longer audit log (t) is the same claim: walk the log once, and tick off the next required approval the moment it appears, regardless of what else happened around it.
Step-by-Step Execution Trace Table
Input s = "abc", t = "ahbgdc" (LeetCode Example 1). i = 0 at the start:
j | t[j] | s[i] (if i < len(s)) | Match? | i after this step |
|---|---|---|---|---|
| 0 | a | a | Yes | 1 |
| 1 | h | b | No | 1 |
| 2 | b | b | Yes | 2 |
| 3 | g | c | No | 2 |
| 4 | d | c | No | 2 |
| 5 | c | c | Yes | 3 |
| End | i == len(s) == 3, so the function returns true |
| 1 | Give s its own claimed-count pointer, i, starting at 0. |
| 2 | Walk t once with j; advance i only when t[j] equals s[i], the next unclaimed character of s. |
| 3 | `i = 0`; `for j in range(len(t)): if i < len(s) and s[i] == t[j]: i += 1`; `return i == len(s)`. |
| 4 | The trap: advancing i on every character of t, not only on a match, makes the final check pass even when s is not really a subsequence of t. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Deciding whether every character of a short string s shows up, in order, somewhere inside a longer string t looks like it needs backtracking or a search over which characters of t to skip, but it does not: walking t once and greedily claiming the next unclaimed character of s the moment it appears always finds a match if one exists. Claiming the earliest available copy of a character is never a mistake, because every later position of t is still free for whatever comes next in s -- a later choice would only leave less of t behind.
🧾 The Analogy: Checking Off a Shopping List While Walking Down One Aisle
Picture a short shopping list, s, and one long aisle of shelves, t, read start to end exactly once. Walk the aisle item by item; the moment the item in front of you matches the next item still unchecked on the list, check it off. Skip every shelf that does not match the next item you need -- it costs nothing to skip, and you never walk the aisle a second time to look for an item you have already found. By the end of the aisle, the list is fully satisfied exactly when every item on it has been checked off, in order.
🔑 Why It Works
Checking off the earliest copy of the next needed item is always at least as good as waiting for a later copy: every shelf after the one just checked off is still available for the rest of the list, so an earlier claim can never cost a later one. Across the whole walk, j visits every character of t exactly once, and i only ever moves forward, so the whole decision costs one pass over t, O(len(t)).
Advancing
ion every character oft, not only on a match (the card's trap): movingi += 1outside theifclaims characters that were never actually matched, so the final checki == len(s)can saytrueeven whensis not really a subsequence oft.Writing
i == len(s) - 1instead ofi == len(s):ireacheslen(s)only once every character ofsis claimed; comparing againstlen(s) - 1rejects a correct full match one claim too early.Checking
s[i] in tinstead of walkingtin order: membership alone has no memory of how far throughtthe previous match reached, so it can accept characters ofsmatched out of order.Treating Append Characters to String to Make Subsequence (LC 2486) as a new algorithm: it is the same claim run the other way -- walk
sonce, claim characters oft, and the answer islen(t)minus the number claimed, since the rest can always be appended to the end ofs.Subtracting from the wrong length on LC 2486's transfer problem: the answer is
len(t) - claimed, notlen(s) - claimed;sis the string being walked,tis the string being claimed.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Two strings, s and t, and the question is whether every character of s appears in t in the same relative order, though not necessarily next to each other. The order matters but the gaps do not, so one forward walk over t can answer it. That is the signal for Greedy Subsequence Match: walk t once and claim the next unclaimed character of s each time it appears.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
i counts how many characters of s are claimed so far, in order. At each t[j], i goes up by one only when i < len(s) and s[i] == t[j]. The earliest available match for s[i] never costs a later character of s its own match, so i == len(s) after the walk means s is a subsequence of t.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Returning
trueas soon as the scan oftfinishes, instead of checkingi: reaching the last index oftonly means the walk is over, not that every character ofswas claimed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Greedy Subsequence Match. I walk t once with j and keep i, the number of characters of s that I have already claimed in order. At each j, if i is still inside s and s at i equals t at j, I advance i by one; otherwise I leave i alone. Taking the earliest available match is always safe, because every later position of t is still free for whatever comes next in s. When the walk ends, s is a subsequence of t exactly when i equals the length of s. The trap is advancing i on every character of t, not only on a match: that claims characters that were never matched, so the final check can say true when it should say false. The walk is O(len(t)) time and
O(1)space.
Complexity & Mathematical Proof
O(len(t))
The for loop runs once over t; each iteration does one comparison and, at most, one increment of i.
O(1)
Nothing is allocated beyond the two integer counters i and j.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "is s a subsequence of t", "deleting some characters", "keep the rest in their original order". One short string checked against one long string, order preserved but gaps allowed: Greedy Subsequence Match, a single pass claiming characters greedily.
, . Budget: time, space -- one pass over the longer string, no extra memory beyond two counters.
Advancing i on every character of t, not only on a match, lets the final check pass even when s is not really a subsequence of t. The follow-up (many strings checked against the same t) changes the cost model: indexing t's letter positions once and binary-searching them per query turns many single-pass scans into one O(n log n) build plus O(m log n) per query, where this card's own approach alone would cost O(q * len(t)) across q queries.
Is Subsequence (LeetCode 392)
You get two strings, s and t. Decide whether s is a subsequence of t: whether every character of s appears somewhere in t, in the same relative order, though not necessarily next to each other. Return true or false.
Worked Examples
s = "abc", t = "ahbgdc"truea, b and c appear in t at positions 0, 2 and 5, in that order.s = "axc", t = "ahbgdc"falset has no x at all, so s cannot be picked out of it.⚖️Formal Constraints & Bounds
0 <= s.length <= 1000 <= t.length <= 104sandtconsist only of lowercase English letters.
Core Insight
Walking t once and claiming the next unclaimed character of s the moment it is seen always finds a match if one exists, because the earliest available match for any character of s never costs a later character of s its own match.
Real-World Scenario & Production Applications
Checking whether a sequence of required approvals (s) all happened, in order, somewhere inside a longer audit log (t) is the same claim: walk the log once, and tick off the next required approval the moment it appears, regardless of what else happened around it.
Step-by-Step Execution Trace Table
Input s = "abc", t = "ahbgdc" (LeetCode Example 1). i = 0 at the start:
j | t[j] | s[i] (if i < len(s)) | Match? | i after this step |
|---|---|---|---|---|
| 0 | a | a | Yes | 1 |
| 1 | h | b | No | 1 |
| 2 | b | b | Yes | 2 |
| 3 | g | c | No | 2 |
| 4 | d | c | No | 2 |
| 5 | c | c | Yes | 3 |
| End | i == len(s) == 3, so the function returns true |
| 1 | Give s its own claimed-count pointer, i, starting at 0. |
| 2 | Walk t once with j; advance i only when t[j] equals s[i], the next unclaimed character of s. |
| 3 | `i = 0`; `for j in range(len(t)): if i < len(s) and s[i] == t[j]: i += 1`; `return i == len(s)`. |
| 4 | The trap: advancing i on every character of t, not only on a match, makes the final check pass even when s is not really a subsequence of t. |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Deciding whether every character of a short string s shows up, in order, somewhere inside a longer string t looks like it needs backtracking or a search over which characters of t to skip, but it does not: walking t once and greedily claiming the next unclaimed character of s the moment it appears always finds a match if one exists. Claiming the earliest available copy of a character is never a mistake, because every later position of t is still free for whatever comes next in s -- a later choice would only leave less of t behind.
🧾 The Analogy: Checking Off a Shopping List While Walking Down One Aisle
Picture a short shopping list, s, and one long aisle of shelves, t, read start to end exactly once. Walk the aisle item by item; the moment the item in front of you matches the next item still unchecked on the list, check it off. Skip every shelf that does not match the next item you need -- it costs nothing to skip, and you never walk the aisle a second time to look for an item you have already found. By the end of the aisle, the list is fully satisfied exactly when every item on it has been checked off, in order.
🔑 Why It Works
Checking off the earliest copy of the next needed item is always at least as good as waiting for a later copy: every shelf after the one just checked off is still available for the rest of the list, so an earlier claim can never cost a later one. Across the whole walk, j visits every character of t exactly once, and i only ever moves forward, so the whole decision costs one pass over t, O(len(t)).
Advancing
ion every character oft, not only on a match (the card's trap): movingi += 1outside theifclaims characters that were never actually matched, so the final checki == len(s)can saytrueeven whensis not really a subsequence oft.Writing
i == len(s) - 1instead ofi == len(s):ireacheslen(s)only once every character ofsis claimed; comparing againstlen(s) - 1rejects a correct full match one claim too early.Checking
s[i] in tinstead of walkingtin order: membership alone has no memory of how far throughtthe previous match reached, so it can accept characters ofsmatched out of order.Treating Append Characters to String to Make Subsequence (LC 2486) as a new algorithm: it is the same claim run the other way -- walk
sonce, claim characters oft, and the answer islen(t)minus the number claimed, since the rest can always be appended to the end ofs.Subtracting from the wrong length on LC 2486's transfer problem: the answer is
len(t) - claimed, notlen(s) - claimed;sis the string being walked,tis the string being claimed.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Two strings, s and t, and the question is whether every character of s appears in t in the same relative order, though not necessarily next to each other. The order matters but the gaps do not, so one forward walk over t can answer it. That is the signal for Greedy Subsequence Match: walk t once and claim the next unclaimed character of s each time it appears.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
i counts how many characters of s are claimed so far, in order. At each t[j], i goes up by one only when i < len(s) and s[i] == t[j]. The earliest available match for s[i] never costs a later character of s its own match, so i == len(s) after the walk means s is a subsequence of t.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Returning
trueas soon as the scan oftfinishes, instead of checkingi: reaching the last index oftonly means the walk is over, not that every character ofswas claimed.
The 60-Second Interview Pitch
Say this out loud before you type a single line
I'd use Greedy Subsequence Match. I walk t once with j and keep i, the number of characters of s that I have already claimed in order. At each j, if i is still inside s and s at i equals t at j, I advance i by one; otherwise I leave i alone. Taking the earliest available match is always safe, because every later position of t is still free for whatever comes next in s. When the walk ends, s is a subsequence of t exactly when i equals the length of s. The trap is advancing i on every character of t, not only on a match: that claims characters that were never matched, so the final check can say true when it should say false. The walk is O(len(t)) time and
O(1)space.
Complexity & Mathematical Proof
O(len(t))
The for loop runs once over t; each iteration does one comparison and, at most, one increment of i.
O(1)
Nothing is allocated beyond the two integer counters i and j.
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "is s a subsequence of t", "deleting some characters", "keep the rest in their original order". One short string checked against one long string, order preserved but gaps allowed: Greedy Subsequence Match, a single pass claiming characters greedily.
, . Budget: time, space -- one pass over the longer string, no extra memory beyond two counters.
Advancing i on every character of t, not only on a match, lets the final check pass even when s is not really a subsequence of t. The follow-up (many strings checked against the same t) changes the cost model: indexing t's letter positions once and binary-searching them per query turns many single-pass scans into one O(n log n) build plus O(m log n) per query, where this card's own approach alone would cost O(q * len(t)) across q queries.