Faangprep Logo
Log inStart free
Browse curriculum

Is Subsequence

Check whether s is a subsequence of t in one pass with two pointers, matching each character of s at its first chance in t.

EasySolve on LeetCode

Problem Understanding

Is Subsequence: return true if s can be made by deleting some (or no) characters from t without changing the order of the rest.

Examples: s = "abc", t = "ahbgdc" returns true; s = "axc", t = "ahbgdc" returns false.

The Intuition: Tick Off s While Reading t

Read t from left to right, keeping a finger on the next character of s you still need. This is a same-direction two pointers scan:

  1. i is the next character of s to find; j walks through t.
  2. If t[j] == s[i], that character is found: move i on.
  3. Move j on either way.
  4. When either string runs out, s is a subsequence exactly if i reached its end.

Taking each match at the first opportunity is safe: an earlier match always leaves more of t for the rest of s.

Interactive Walkthrough

s is on top and t below, with i and j marking where each pointer is. Every match shades the found character in s and the position in t where it was found; try "Wrong order" to see order matter.

Dry Run Table

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

j t[j] s[i] Action i
0 a a match 1
1 h b skip 1
2 b b match 2
3 g c skip 2
4 d c skip 2
5 c c match 3

i = 3 = len(s): true.

The Solution Template

Two pointers in the same direction.

Is Subsequence Code
1var isSubsequence = function(s, t) {
2    let i = 0;
3    for (let j = 0; j < t.length && i < s.length; j++) {
4        if (s[i] === t[j]) i++;
5    }
6    return i === s.length;
7};

Edge Cases & Common Mistakes

  • Empty s: always a subsequence; i is already at the end.
  • s longer than t: t runs out first; return false.
  • Order matters: "ba" is not a subsequence of "abc", even though both letters appear.
  • Searching t from the start for each character: that loses the order and can reuse characters; keep j moving forward only.

Summary

Walk t once with j, and move i through s only when t[j] matches s[i]. Matching greedily at the first chance is always safe. s is a subsequence exactly when i reaches its end. O(len t) time, O(1) space.

More practice: DSA interview questions with answers · patterns cheat sheet

Previous

Squares of a Sorted Array

Next

Valid Palindrome II

The approach, step by step

  1. Start both pointers at 0

    i points into s, j into t.

  2. Walk t

    While both are in range: if s[i] == t[j], move i on. Always move j on.

  3. Check i

    s is a subsequence exactly when i reached the end of s.

Frequently asked questions

Why is matching at the first chance always safe?

If s[i] can be matched at an earlier position of t, using that position leaves at least as much of t for the rest of s as any later match would. So greedily taking the first match never rules out a solution.

What is the difference between a subsequence and a substring?

A substring must be contiguous. A subsequence keeps the order of the characters but may skip any in between: "ace" is a subsequence of "abcde" but not a substring.

What about the follow-up with many s strings?

If t is fixed and you get many queries, store the positions of each letter in t and binary search for the next position after the current one. Each query then costs O(len(s) · log len(t)).

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description