Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence is a new string formed by deleting some characters (possibly none) from the original string, without changing the order of the remaining characters. For example, "ace" is a subsequence of "abcde", but "aec" is not.

Constraints:

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

Follow-up: Suppose there are billions of incoming strings s1, s2, ..., sk, and you must check each one against the same t. How would you change your code?

What Is a Subsequence?

Think of s as a shopping list and t as the shop. You walk through the shop in one direction and tick off each item when you see it. You can never walk back. If you tick off every item, s is a subsequence of t.

1s = "abc", t = "ahbgdc"  → true   (a, b, c appear in this order)
2s = "aec", t = "abcde"   → false  (e only appears after c, so the order breaks)

Order matters. Having all the letters is not enough.

We will solve this in three ways:

1. Brute Force: try every choice.
2. Two Pointers (Optimal): one pass over t. Best for a single check.
3. Next-Position Table (Most Optimal for the follow-up): prepare t once, so every check is very fast.

Approach 1: Brute Force

check(i, j) answers: "can s from position i be found inside t from position j?"

At each letter of t, we try both choices when the letters match:

• Take it: match s[i] with t[j], and move both forward.
• Skip it: ignore t[j], and move only j forward.

If the letters do not match, we can only skip.

class Solution {
    private boolean check(int i, int j, String s, String t) {
        if (i == s.length()) {
            return true;    // every letter of s was found
        }
        if (j == t.length()) {
            return false;   // t ended before s was finished
        }

        boolean skip = check(i, j + 1, s, t);

        if (s.charAt(i) == t.charAt(j)) {
            boolean take = check(i + 1, j + 1, s, t);
            return take || skip;
        }
        return skip;
    }

    public boolean isSubsequence(String s, String t) {
        return check(0, 0, s, t);
    }
}

Time: O(2^n) in the worst case, where n is the length of t. When many letters match and the answer is false, both choices are explored at every step.

Space: O(n) for the recursion stack.

This is correct but too slow. Notice something: taking a match is never worse than skipping it. That removes the second choice.

Approach 2: Two Pointers (Optimal)

Taking the earliest possible match leaves the most letters of t for the rest of s. Waiting for a later match can never help. So we always take a match right away, and the choice disappears.

A pointer is just a number that remembers a position.

• i points to the next letter we need in s.
• j walks through t, one letter at a time.

Whenever t[j] equals s[i], we move i forward. We always move j forward. We never move j backward, so the order is respected.

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;   // next letter we need from s

        for (int j = 0; j < t.length() && i < s.length(); j++) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
        }

        // If i reached the end of s, we found every letter in order
        return i == s.length();
    }
}

Time: O(n), one pass over t.

Space: O(1), just two numbers.

Dry Run

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

1j   t[j]   needs   action        i after
20    a      a      match            1
31    h      b      skip             1
42    b      b      match            2
53    g      c      skip             2
64    d      c      skip             2
75    c      c      match            3
8 
9i = 3 = length of s → true

Two small details:

• If s is empty, i == s.length() is true from the start. An empty string is a subsequence of every string.
• The loop stops as soon as i reaches the end of s, so we never scan extra letters of t.

Approach 3: Next-Position Table (Most Optimal for the Follow-up)

Now we have up to 1 billion strings to check against the same t.

Here is what breaks. Two pointers scans t from the start for every string:

1One check:         up to 10,000 steps
21 billion checks:  1,000,000,000 × 10,000 = 10,000,000,000,000 steps ✗

We repeat the same work on t every time. The fix is to prepare t once, so each check becomes cheap. This is the same idea as an index in a database.

Build a table where next[j][c] means: "the first position at or after j where letter c appears in t". If there is none, store n (the length of t).

1t = "ahbgdc"   (n = 6)
2 
3next[0]: a→0  b→2  c→5  d→4  g→3  h→1  others→6
4next[1]: a→6  b→2  c→5  d→4  g→3  h→1  others→6
5next[2]: a→6  b→2  c→5  d→4  g→3  h→6  others→6
6...

We build it from the end of t backward. Each row is a copy of the row after it, with one change: the letter at position j now points to j.

To check s, keep pos, the next position we may use. For each letter, look up next[pos][letter]. If it equals n, the letter is missing, so return false. Otherwise, set pos to that position plus one.

1s = "abc", t = "ahbgdc"
2a: next[0][a] = 0  → pos = 1
3b: next[1][b] = 2  → pos = 3
4c: next[3][c] = 5  → pos = 6
5All found → true
6 
7s = "axc"
8a: next[0][a] = 0  → pos = 1
9x: next[1][x] = 6 = n → missing → false

import java.util.Arrays;

class FastSubsequenceChecker {
    private final int[][] next;
    private final int n;

    // Prepare t once
    public FastSubsequenceChecker(String t) {
        n = t.length();
        next = new int[n + 1][26];
        Arrays.fill(next[n], n);   // no letters left, so every letter is missing

        for (int j = n - 1; j >= 0; j--) {
            next[j] = next[j + 1].clone();
            next[j][t.charAt(j) - 'a'] = j;
        }
    }

    // Called once for every incoming s
    public boolean isSubsequence(String s) {
        int pos = 0;

        for (int k = 0; k < s.length(); k++) {
            int found = next[pos][s.charAt(k) - 'a'];
            if (found == n) {
                return false;
            }
            pos = found + 1;
        }
        return true;
    }
}

Preparation: O(26 × n), done once.

Each check: O(m), one lookup per letter of s. That is at most 100 steps.

Space: O(26 × n), about 260,000 numbers for n = 10,000.

If memory is tight, store a sorted list of positions for each letter and use binary search instead. Each check becomes O(m log n), but memory drops to O(n).

Comparing All Approaches

Complexity

How to Explain It in an Interview