We need to check whether every character of s appears in t, in the same order, but not necessarily consecutively. We can skip characters in t, but we cannot rearrange them. For example, "ace" is a subsequence of "abcde" because a, c, and e appear in that order, while "aec" is not, since e comes before c in the target.

The follow-up changes the problem. Checking one string against t is a single linear scan. But if we need to check a billion strings against the same fixed t, re-scanning t for each one is wasteful. Preprocessing t once lets each query do less work.

Key Constraints:

Intuition

Walk through both strings with one pointer for s and one for t. When the current characters match, advance the pointer on s. Advance the pointer on t on every step. If the s pointer reaches the end before t runs out, every character of s was matched in order, so s is a subsequence.

The strategy is greedy: whenever a character of t matches the character of s we are looking for, we consume it immediately rather than saving it for later. This is safe because matching the earliest possible occurrence in t leaves the longest remaining suffix of t to match the rest of s. Any valid matching that skips this occurrence and uses a later one can be rewritten to use the earlier occurrence instead, so the greedy choice never loses a solution that a delayed choice would have found.

Algorithm

Example Walkthrough

Code

For a single query this is optimal: each character of both strings is examined at most once. The limitation appears under the follow-up, where many queries run against the same t. Each query re-scans t from the start. The next approach preprocesses t once so that each query can locate matches by binary search instead of a full scan.

Intuition

When t is fixed and many query strings run against it, we can preprocess t once and reuse the result across all queries. For each character of the alphabet, store the sorted list of indices where that character appears in t. Then, for each character of s, find the next valid position with a binary search over that character's index list instead of scanning t.

For example, if t = "ahbgdc", we'd build this index map:

To check if s = "abc" is a subsequence, we start at position -1 (before the string). For 'a', binary search for the smallest index > -1 in [0]. That gives us 0. For 'b', search for the smallest index > 0 in [2]. That gives us 2. For 'c', search for the smallest index > 2 in [5]. That gives us 5. We found valid positions for all characters, so it's a subsequence.

Algorithm

Example Walkthrough

Code

Each query is O(n log m) because of the per-character binary search. The next approach removes the log factor by precomputing, for every position in t and every character, where the next occurrence of that character is, turning each lookup into a constant-time table read.

Intuition

Precompute a jump table for t: for every position j and every character c, store the index of the next occurrence of c at or after position j. Each character lookup during a query then becomes a constant-time table read.

The table is built by scanning t from right to left. The right-to-left order matters because the next occurrence of a character at position j depends only on what comes after j, which has already been computed. At position j, the next occurrence of t[j] is j itself. For every other character, the next occurrence at j is the same as at j + 1, so we copy row j + 1 and overwrite the single entry for t[j]. This fills the entire table in O(26 * m) time.

To check a query, start at position 0 in t. Look up the next occurrence of s[0], move one past it, look up the next occurrence of s[1] from there, and continue. Each lookup is O(1), so a query costs O(n).

Algorithm

Example Walkthrough

Code