#392 Is Subsequence

frequently reported atAmazon Google Bloomberg

the problem

In plain words

Return true if s is a subsequence of t: you can delete some characters of t (or none) and, without changing the order of the rest, get s.

in s = "abc", t = "ahbgdc"

out true

in s = "axc", t = "ahbgdc"

out false

There is no 'x' in t.

0 ≤ s.length ≤ 100
0 ≤ t.length ≤ 10⁴
Lowercase English letters

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternTwo pointers (one per sequence)

Walk t once and tick off s's next character whenever you see it. Matching as early as possible never hurts — it leaves the most of t for the rest of s.

solutions

From brute force to optimal

ok[i][j] says whether the first i characters of s fit inside the first j characters of t.

ok[0][j] = true: the empty string fits anywhere.
ok[i][j] = ok[i][j − 1] (skip t's character) or (s[i − 1] == t[j − 1] and ok[i − 1][j − 1]) (use it).
The answer is ok[|s|][|t|].

timeO(|s|·|t|)

Every cell once: up to 100 × 10⁴ = 10⁶.

spaceO(|s|·|t|)

The whole table.

javajava.util.*

1class Solution {2    public boolean isSubsequence(String s, String t) {3        int n = s.length(), m = t.length();4        // ok[i][j]: the first i chars of s are a subsequence of the first j chars of t5        boolean[][] ok = new boolean[n + 1][m + 1];6        for (int j = 0; j <= m; j++) ok[0][j] = true;   // the empty string is in everything7        for (int i = 1; i <= n; i++)8            for (int j = 1; j <= m; j++)9                ok[i][j] = ok[i][j - 1] || (s.charAt(i - 1) == t.charAt(j - 1) && ok[i - 1][j - 1]);10        return ok[n][m];11    }12}

i points at the next character of s to find; scan t once.

i = 0.
For each character of t: if it equals s[i], i++.
Return i == |s|.

timeO(|t|)

One pass over t.

spaceO(1)

One index.

javajava.util.*

1class Solution {2    public boolean isSubsequence(String s, String t) {3        int i = 0;                                       // next char of s to find4        for (int j = 0; j < t.length() && i < s.length(); j++) {5            if (s.charAt(i) == t.charAt(j)) i++;         // matched: look for the next one6        }7        return i == s.length();                          // found every char, in order8    }9}

For many s and one fixed t: store where each letter occurs in t, then jump with binary search.

Once: for each letter, the sorted list of its positions in t.
For each character of s: binary search its list for the first position after the previous match.
No such position → false.

timeO(|t|) once + O(|s| log |t|) per query

Building the lists touches t once; each character of s is one binary search.

spaceO(|t|)

Every position of t is stored once.

javamany queries, one tjava.util.*

1class IndexLists {2    private final List<List<Integer>> where = new ArrayList<>();3 4    /** Pay O(|t|) once: for each letter, the sorted positions where it occurs in t. */5    IndexLists(String t) {6        for (int c = 0; c < 26; c++) where.add(new ArrayList<>());7        for (int j = 0; j < t.length(); j++) where.get(t.charAt(j) - 'a').add(j);8    }9 10    /** Each query: O(|s| log |t|) — jump to the first position after the previous match. */11    boolean isSubsequence(String s) {12        int after = -1;13        for (char c : s.toCharArray()) {14            List<Integer> list = where.get(c - 'a');15            int pos = Collections.binarySearch(list, after + 1);16            if (pos < 0) pos = -pos - 1;                 // not found → insertion point = first index > after17            if (pos == list.size()) return false;        // no c after the previous match18            after = list.get(pos);19        }20        return true;21    }22}

in the room

How to say it in the interview

talk track

Clarify subsequence vs substring: order matters, gaps are allowed.
Explain the greedy choice: taking the earliest match can only leave more room for the rest of s.
LeetCode's follow-up (a huge number of s against one t) is the cue for index lists + binary search.

traps

Reading s.charAt(i) after s is fully matched (or when s is empty): guard with i < s.length().
Treating it as substring search (t.contains(s)): gaps are allowed here.

what they ask next

Follow-ups

Number of Matching Subsequences (LC 792): many words against one string?

Index lists + binary search per word, or bucket the words by the letter each one is waiting for and scan the string once.

Longest Common Subsequence (LC 1143)?

When neither string has to fit fully, greed fails; you need the DP table (dynamic-programming chapter).

before you submit

Edge cases to test

Empty s → true: the empty string is a subsequence of anything.
Empty t with a non-empty s → false.
Right letters, wrong order: "ba" in "ab" → false.
Repeated letters: "aa" in "baab" → true; each match must come after the previous one.

practise next