Free lesson · DSA Mastery - Interview Prep, End to End

Is Subsequence

Medium7 min readdsastrings

Is Subsequence

Is Subsequence is a clean two-pointer scanning problem. Given a candidate subsequence s and a longer string t, walk through t and check whether s can be reconstructed by picking characters from t in order. The algorithm is short and obvious - the interesting part is the follow-up question, which transforms the problem completely.

The naive solution is what you'll implement in 30 seconds. The follow-up question - "what if you had many queries against the same t?" - opens up an entire family of preprocessing-based optimizations. This is one of the cleanest examples of "the right algorithm depends on the access pattern."

The Problem

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

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

Example 1:

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

Explanation: "abc" can be formed from "ahbgdc" by keeping indices 0, 2, 5.

Example 2:

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

Explanation: There's no 'x' in t.

Constraints:

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

Follow-up: Suppose there are lots of incoming s, say s1, s2, ..., sk, where k >= 10^9, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Approach

Two pointers, both starting at 0:

• i indexes into s (the subsequence to find)
• j indexes into t (the longer string to scan)

Walk j through t. Whenever t[j] == s[i], advance i (we found a match for the current required character). Always advance j.

When i reaches s.length(), we've found every character of s in order - return true. If j reaches t.length() first, we ran out of t before finishing s - return false.

graph TD
    A["i = 0, j = 0"] --> B["While i < s.len AND j < t.len"]
    B --> C{"s[i] == t[j]?"}
    C -->|Yes| D["i++ (next required char)"]
    C -->|No| E["skip"]
    D --> F["j++ (next position in t)"]
    E --> F
    F --> G{"i < s.len AND j < t.len?"}
    G -->|Yes| B
    G -->|No| H{"i == s.len?"}
    H -->|Yes| I["Return true"]
    H -->|No| J["Return false"]
    
    style A fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style B fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style C fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style D fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style E fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style F fill:#4338ca,stroke:#6366f1,color:#f1f5f9
    style G fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style H fill:#b45309,stroke:#f59e0b,color:#f1f5f9
    style I fill:#16a34a,stroke:#10b981,color:#f1f5f9
    style J fill:#dc2626,stroke:#ef4444,color:#f1f5f9

This diagram shows the two-pointer approach. We start both pointers at zero. We walk through t with j. When s at i matches t at j, we advance i. Always advance j. When i reaches the length of s, we have found every required character in order and return true. If j reaches the end of t first, return false.

Code Implementation

public static 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();
}

// Usage:
// System.out.println(isSubsequence("abc", "ahbgdc"));  // true
// System.out.println(isSubsequence("axc", "ahbgdc"));  // false

This Java code implements Is Subsequence with two pointers. We walk j through t. Whenever t at j matches s at i, we advance i. We always advance j. After the loop, we check if i reached the length of s. If so, every character of s was found in order.

The clean termination condition: the loop exits when either pointer reaches its end. We then check whether s was fully consumed.

Walkthrough

Trace on s = "abc", t = "ahbgdc".

Initial: i=0, j=0.

j=0: t[0]='a', s[0]='a'. Match. i=1, j=1.
j=1: t[1]='h', s[1]='b'. No match. j=2.
j=2: t[2]='b', s[1]='b'. Match. i=2, j=3.
j=3: t[3]='g', s[2]='c'. No match. j=4.
j=4: t[4]='d', s[2]='c'. No match. j=5.
j=5: t[5]='c', s[2]='c'. Match. i=3, j=6.

i == s.length(). Loop exits.
Return i == 3 == s.length() → true.

Result: true.

Trace on s = "axc", t = "ahbgdc":

Initial: i=0, j=0.

j=0: t[0]='a', s[0]='a'. Match. i=1, j=1.
j=1: t[1]='h', s[1]='x'. No match. j=2.
j=2: t[2]='b', s[1]='x'. No match. j=3.
j=3: t[3]='g', s[1]='x'. No match. j=4.
j=4: t[4]='d', s[1]='x'. No match. j=5.
j=5: t[5]='c', s[1]='x'. No match. j=6.

j == t.length(). Loop exits.
Return i == 1, which is not s.length()=3 → false.

Result: false. We never found 'x' in t.

Complexity Analysis

Why It Is O(n)

Each iteration advances j by 1. The loop terminates when either pointer reaches its end, so total iterations is at most t.length(). Total work: O(|t|).

If |s| > |t|, the loop runs |t| iterations and returns false. If |s| <= |t|, also at most |t| iterations. Either way, linear in t's length.

Why It Is O(1) Space

Two integer counters. No auxiliary data.

Variations & Follow-ups

The Follow-up: Many Queries on the Same t

When you have many s values to check against a single t, the O(|t|) per query becomes prohibitive. Preprocess t once to enable faster queries.

Approach: Index Map

For each character c, store a sorted list of positions where c appears in t. Then for each query s, walk through s while maintaining the "current position in t." For each s[i], binary-search the list for s[i] for the smallest position greater than the current position. If found, update the current position. If not, return false.

public static class IsSubsequenceQueries {
    private final List<List<Integer>> indices;
    
    public IsSubsequenceQueries(String t) {
        indices = new ArrayList<>(26);
        for (int i = 0; i < 26; i++) indices.add(new ArrayList<>());
        for (int j = 0; j < t.length(); j++) {
            indices.get(t.charAt(j) - 'a').add(j);
        }
    }
    
    public boolean isSubsequence(String s) {
        int curr = -1;  // No position chosen yet
        for (int i = 0; i < s.length(); i++) {
            List<Integer> positions = indices.get(s.charAt(i) - 'a');
            // Find smallest position > curr
            int idx = upperBound(positions, curr);
            if (idx == positions.size()) return false;
            curr = positions.get(idx);
        }
        return true;
    }
    
    private int upperBound(List<Integer> list, int target) {
        int lo = 0, hi = list.size();
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (list.get(mid) <= target) lo = mid + 1;
            else hi = mid;
        }
        return lo;
    }
}

Preprocessing: O(|t|) time and O(|t|) space. Per query: O(|s| log |t|).

For k queries, total time: O(|t| + k * |s| log |t|), much better than k * O(|t|) when |s| << |t|.

This is the classic answer to the follow-up. Mention preprocessing for repeated queries; it's a strong signal you understand amortized cost.

Another approach: Successor Table (DP)

Precompute a table next[i][c] = the smallest position j >= i such that t[j] = c, or -1 if no such j exists. Then per-query traversal is O(|s|).

int[][] next = new int[t.length() + 1][26];
for (int c = 0; c < 26; c++) next[t.length()][c] = -1;
for (int i = t.length() - 1; i >= 0; i--) {
    for (int c = 0; c < 26; c++) {
        next[i][c] = (t.charAt(i) - 'a' == c) ? i : next[i + 1][c];
    }
}

Preprocessing: O(|t| * 26). Per query: O(|s|). Best for very long s and many queries, since each query is linear in s.

What if s could be empty?

The empty string is a subsequence of anything. Algorithm: i=0 starts at s.length()=0, so the loop doesn't execute. We return i == s.length() → true. Correct.

What if t is empty (but s is not)?

j=0 = t.length(), loop doesn't execute, i stays 0 < s.length(). Returns false. Correct (can't form a non-empty subsequence from an empty string).

What if both are empty?

i=0 = s.length(). Returns true. Correct.

What about edge cases?

• s longer than t: Eventually j reaches t.length() before i reaches s.length(). Returns false.
• s equals t: Every character matches. Returns true.
• s is a single character that appears in t: The first occurrence advances i to 1, then loop exits at j = t.length() or earlier. Returns true.
• s has repeated characters: Each occurrence in s needs its own match in t. The algorithm handles this naturally because i only advances when matched.

Common Interview Pitfalls

• Forgetting the final check i == s.length(). Without it, you'd return true if the loop exited for any reason - including "ran out of t before finishing s." The post-loop check distinguishes "finished s" from "ran out of t."
• Advancing both pointers always. The correct behavior is: always advance j, advance i only on match. Some candidates advance both unconditionally and produce wrong results.
• Trying to use DP for the single-query case. DP works but is O(|s| * |t|). The two-pointer scan is O(|t|), strictly better.
• Missing the follow-up's significance. When asked "what about many queries?", the candidate who reaches for preprocessing immediately signals algorithmic maturity. The candidate who tries to optimize the linear scan further (it's already optimal for a single query) signals confusion.

Why This Problem Matters

Is Subsequence is one of those problems where the first answer is trivial but the follow-up reveals depth. The two-pointer scan is easy. The "preprocess once, query many times" approach is what separates a routine answer from a memorable one.

The pattern "amortize over many queries by preprocessing" appears in:

• Range Sum Queries - prefix sums for O(1) queries after O(n) preprocessing.
• LCA in Trees - Euler tour + RMQ for O(1) LCA queries.
• String Hash for Repeated Substring Queries - polynomial hashing.

Whenever you see "given many queries against a fixed structure," think preprocessing.

The next topic, Longest Common Prefix, returns us to a simple but classic problem with several solution approaches worth knowing.

Back to DSA Mastery - Interview Prep, End to End