Is Subsequence — Two Pointer Greedy Match at Google and Amazon

Problem Statement#

Given two strings s and t, return true if s is a subsequence of t, otherwise return false. A subsequence is formed by deleting some characters from t without disturbing the relative order of the remaining characters.

Constraints:

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• s and t consist of lowercase English letters

Input:  s = "abc", t = "ahbgdc"
Output: true

Input:  s = "axc", t = "ahbgdc"
Output: false

Why This Problem Matters#

LeetCode 392 Is Subsequence is a Google and Amazon favorite because the optimal solution is a clean two pointer greedy walk while the more general follow-up requires preprocessing or DP. Interviewers often ask the easy version first to gauge fluency, then escalate to the streaming version where you must answer many subsequence queries against the same t.

Meta has been seen using this problem to lead into LC 1143 Longest Common Subsequence, asking the candidate to first solve subsequence checking and then to solve LCS by extending the same idea with DP.

The two pointer greedy match here is the same pattern that drives LC 524 Longest Word in Dictionary Through Deleting and LC 792 Number of Matching Subsequences (with optimization).

The Core Insight#

Walk both strings with a pointer in each. Always advance the pointer in t. Advance the pointer in s only when the current characters match. If the s pointer reaches the end, every character of s has been matched in order, so s is a subsequence of t.

The greedy choice is safe: matching as early as possible never reduces future opportunities. If a character in s matches at position i in t and also at a later position j, taking i leaves more of t for the rest of s, which can only help.

The algorithm runs in O(m + n) time and O(1) space, where m = len(s) and n = len(t).

Visual Dry Run#

For s = "abc", t = "ahbgdc":

Solution (Optimal)#

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i = 0
        for ch in t:
            if i < len(s) and s[i] == ch:
                i += 1
        return i == len(s)

var isSubsequence = function(s, t) {
    let i = 0;
    for (const ch of t) {
        if (i < s.length && s[i] === ch) {
            i++;
        }
    }
    return i === s.length;
};

Time: O(m + n) — single pass through t Space: O(1) — two indices

Common Mistakes#

• Returning i === t.length instead of i === s.length
• Advancing the s pointer on the no-match branch, accidentally skipping characters
• Building all subsequences of t and checking membership, which is O(2^n) and a hard rejection
• Assuming s length is greater than t length and short-circuiting incorrectly
• Forgetting the empty s case which should return true

Interview Tips#

• State the greedy invariant: "Matching the leftmost occurrence is always safe because it leaves more of t for later"
• Walk through an example where s contains a character not in t to show the failure case
• Mention the streaming follow-up before the interviewer asks: "If we had many s queries against the same t, we would preprocess t into a per-character index list and binary search"
• Compare with LC 1143 LCS to show that subsequence checking is the simpler greedy version of an O(m * n) DP

Follow-up Questions#

• What if there are many s queries against one large t? (Hint: precompute character to indices, binary search)
• How would you find the longest common subsequence? (Hint: LC 1143, O(m * n) DP)
• How do you list all subsequences? (Hint: 2^n recursion, infeasible for large n)
• What if you can delete from both strings? (Hint: LC 583, DP based on LCS)
• How would you check if s is a subsequence of t with at most k mismatches? (Hint: extend the DP with a mismatch counter)

Key Takeaways#

• LeetCode 392 Is Subsequence uses a two pointer greedy walk in O(m + n) time and O(1) space
• Always advance the t pointer; advance the s pointer only on a match
• Greedy leftmost matching is provably safe and optimal for subsequence checking
• Pattern extends to LC 524 Longest Word Through Deleting and LC 792 with preprocessing
• For many subsequence queries against the same t, preprocess into per-character index lists and binary search
• Google, Amazon, and Meta use this as a phone screen warm-up before LCS or LIS
• Empty s always returns true; this is an easy edge case to forget