Is Subsequence

EasyStrings · Two Pointers🧩 String Manipulation LeetCode #392 ↗Updated Oct 30, 2026

Problem

Given strings s and t, decide whether s can be obtained from t by deleting some (possibly zero) characters without reordering the rest — i.e. whether s is a subsequence of t.

Inputs="abc", t="ahbgdc"Outputtrue

Inputs="axc", t="ahbgdc"Outputfalse

0 ≤ |s| ≤ 100 · 0 ≤ |t| ≤ 10⁴ · lowercase letters · Follow-up: billions of s queries against one t.

Try it yourself

Java

class Solution {
    public boolean isSubsequence(String s, String t) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Matching greedily is safe: using the earliest occurrence of each s character in t leaves the most room for the remaining characters.

PatternString Manipulation

Instinct Reading, comparing or rebuilding text character by character? Walk indices on a char[] and build output with a StringBuilder, never with + in a loop.

Memory hack Chars in an array, pointers on the ends, builder at the back - strings are just arrays wearing a costume.

Open the String Manipulation guide →

Approaches

Brute ForceLCS Dynamic Programming

Time O(n·m)Space O(n·m)

s is a subsequence of t iff LCS(s, t) == |s|. Fill the classic table: on a match extend the diagonal, otherwise take the max of skipping a character from either string.

Java

public boolean isSubsequence(String s, String t) {
    int n = s.length(), m = t.length();
    int[][] dp = new int[n + 1][m + 1];
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s.charAt(i - 1) == t.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1] + 1;
            else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[n][m] == n;
}

Correct but heavy — solves a harder problem than needed.

BetterTwo Pointers (Greedy Scan)

Time O(n + m)Space O(1)

Walk t with j; whenever t[j] equals s[i], advance i. If i reaches |s|, every character was matched in order. Best possible for a single query.

Java

public boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
        if (s.charAt(i) == t.charAt(j)) i++;
        j++;
    }
    return i == s.length();
}

Dry runs="abc", t="ahbgdc"

j t pointer changed

j=0
a
j
h

b

g

d

c

match a → i=1
j=1
a

h
j
b

g

d

c

h≠b → skip
j=2
a

h

b
j
g

d

c

match b → i=2
j=3,4
a

h

b

g

d
j
c

g, d ≠ c → skip
j=5
a

h

b

g

d

c
j
match c, i=3 ✔

Optimal for one query, but rescans all of t for every new s.

OptimalIndex Lists + Binary Search (Follow-up)

Time O(m) once + O(n log m)/querySpace O(m)

Preprocess t once: for each letter, the sorted list of its positions. For each s character, binary-search the first position after the previous match. Per query cost no longer depends linearly on |t|.

Java

public boolean isSubsequence(String s, String t) {
    List<List<Integer>> pos = new ArrayList<>(); // build once per t, reuse
    for (int c = 0; c < 26; c++) pos.add(new ArrayList<>());
    for (int j = 0; j < t.length(); j++) pos.get(t.charAt(j) - 'a').add(j);
    int prev = -1;
    for (char ch : s.toCharArray()) {
        List<Integer> list = pos.get(ch - 'a');
        int k = Collections.binarySearch(list, prev + 1);
        if (k < 0) k = -k - 1; // insertion point = first index > prev
        if (k == list.size()) return false;
        prev = list.get(k);
    }
    return true;
}

Best when t is fixed and many s arrive; overkill for one query.

Pro tip

A next[j][c] table (next index of letter c at or after j) makes each query O(n) at the cost of O(26·m) memory.

At a glance

Level	Approach	Time	Space
Brute Force	LCS Dynamic Programming	`O(n·m)`	`O(n·m)`
Better	Two Pointers (Greedy Scan)	`O(n + m)`	`O(1)`
Optimal	Index Lists + Binary Search (Follow-up)	`O(m) once + O(n log m)/query`	`O(m)`

Common pitfalls

Advancing the s pointer on a mismatch — only t's pointer always moves.
Forgetting that an empty s is always a subsequence (return true).
Confusing subsequence with substring — characters need not be contiguous.

Interview tips

Justify the greedy: earliest match never hurts later matches.
Bring up the follow-up yourself and sketch the binary-search preprocessing.
Note the DP view links to LCS / Edit Distance if asked to generalise.

Pattern

Two pointers across two sequences → match one sequence inside another in order.

My notes saved in this browser