Problem Overview
LeetCode 392 — Is Subsequence asks you to determine whether string s is a subsequence of string t. A subsequence preserves relative order but does not require contiguous characters: you can delete characters from t (without reordering the rest) to obtain s.
The follow-up challenge escalates the problem significantly: given a fixed t and a large number of incoming s strings — potentially tens of thousands — answer each query efficiently. A naive O(|s|*|t|) check per query becomes unacceptable when the query volume is large.
This problem sits at the intersection of two classic techniques: the greedy two-pointer scan for the basic case, and binary search on preprocessed index lists for the follow-up. Understanding both variants is essential for coding interviews, particularly when follow-ups probe your ability to optimize for repeated queries.
- Return true if s is a subsequence of t — same relative order, not necessarily contiguous
- Characters from t can be skipped but not reordered
- Basic case: single s against one t — two pointers suffice in O(|s|+|t|)
- Follow-up: many s strings against the same fixed t — preprocessing t is required
- Follow-up preprocessing builds a map from each character to its sorted list of indices in t
- Each follow-up query uses binary search, costing O(|s| log |t|) per s string
Two-Pointer Greedy
Place pointer i at the start of s and pointer j at the start of t. At each step: if s[i] equals t[j], both characters match — advance i to seek the next character of s, and advance j to move past the matched character in t. If they do not match, advance only j to scan forward in t for the next candidate match.
Continue until either i reaches the end of s (all characters matched — return true) or j reaches the end of t (exhausted t without matching all of s — return false). The result is a single left-to-right scan of t with at most |s| advances of i and at most |t| advances of j.
Time complexity is O(|s| + |t|) in the worst case with O(1) extra space. No auxiliary data structures are needed — just two integer indices and the two input strings.
Greedy Matching the First Occurrence Is Always Optimal
The greedy approach works because matching the first occurrence of each character in t is always optimal: skipping an earlier match can never help. If you pass over the first occurrence of s[i] in t and match a later one instead, you have consumed more of t unnecessarily, leaving fewer characters ahead for the remaining characters of s. The greedy choice — match as early as possible — maximizes remaining flexibility.
Algorithm Steps
Initialize i = 0 and j = 0. The outer loop runs while both i < len(s) and j < len(t). Inside the loop, compare s[i] with t[j]: if equal, increment i to advance to the next character of s. Regardless of match or mismatch, always increment j to advance through t.
After the loop exits — either because i reached len(s) or j reached len(t) — return whether i == len(s). If i has reached the end of s, every character of s was matched in order within t, confirming s is a subsequence.
The invariant throughout: i is the count of characters of s matched so far. The loop terminates when either all of s is matched (i == len(s)) or t is exhausted (j == len(t)). Checking i == len(s) at the end captures both exit conditions correctly.
- 1i = 0, j = 0
- 2while i < len(s) and j < len(t):
- 3 — if s[i] == t[j]: i += 1 (advance s pointer on match)
- 4 — j += 1 (always advance t pointer)
- 5return i == len(s)
Follow-Up: Many s Queries
When t is fixed and many different s strings arrive as queries, the two-pointer approach reruns a full O(|t|) scan for every s. With k incoming queries, the total cost is O(k * |t|), which is prohibitive when k and |t| are both large.
Preprocess t once: build a dictionary mapping each character to the sorted list of indices where it appears in t. For the string t = "abcde", this produces {'a': [0], 'b': [1], 'c': [2], 'd': [3], 'e': [4]}. This O(|t|) preprocessing step is done once and shared across all queries.
For each incoming s, maintain a current position pointer into t (starting at 0). For each character c in s, binary search the sorted index list for c to find the smallest index in t that is >= the current position. If found, advance the current position past that index. If not found, s is not a subsequence. Each character lookup costs O(log |t|), making each query O(|s| log |t|) total.
Preprocessing Amortizes the Cost Across Many Queries
The follow-up transforms the problem from O(k * |t|) for k queries to O(|t| + k * |s| * log|t|). The O(|t|) preprocessing cost is paid once and amortized across all queries. When k is large and |s| is short (e.g., thousands of 5-character strings against a long fixed t), this is vastly more efficient than re-scanning t for each query.
Walk-Through Example
Trace s = "ace" against t = "abcde" using the two-pointer approach. Initialize i = 0 (pointing at 'a' in s), j = 0 (pointing at 'a' in t).
j=0: t[0]='a' matches s[0]='a' → i becomes 1. j=1: t[1]='b' does not match s[1]='c' → j advances only. j=2: t[2]='c' matches s[1]='c' → i becomes 2. j=3: t[3]='d' does not match s[2]='e' → j advances only. j=4: t[4]='e' matches s[2]='e' → i becomes 3.
After the loop, i = 3 = len(s) = 3, so return true. All three characters of s were matched in order within t. The matched positions were indices 0, 2, and 4 of t — a valid subsequence alignment.
- 1i=0 ('a'), j=0 ('a'): match → i=1, j=1
- 2i=1 ('c'), j=1 ('b'): no match → j=2
- 3i=1 ('c'), j=2 ('c'): match → i=2, j=3
- 4i=2 ('e'), j=3 ('d'): no match → j=4
- 5i=2 ('e'), j=4 ('e'): match → i=3, j=5
- 6Loop exits: i=3 == len(s)=3 → return True
Code Walkthrough: Python and Java
Python two-pointer: def isSubsequence(s, t): i = j = 0; while i < len(s) and j < len(t): if s[i] == t[j]: i += 1; j += 1; return i == len(s). Five lines; O(|s|+|t|) time, O(1) space. The follow-up Python version uses collections.defaultdict(list) to build the index map, then bisect.bisect_left to find the earliest matching index >= current position for each character of s.
Java two-pointer: 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(); }. For the follow-up in Java, build a Map<Character, List<Integer>> from t, then use Collections.binarySearch or a custom binary search to find the leftmost index >= current position.
Both implementations share the same logic: scan t with j always advancing and i advancing only on match. The follow-up variants replace the j scan with a binary search into precomputed lists — same matching logic, but indexing into sorted lists rather than scanning sequentially. Time for basic: O(|t|). Time for follow-up per query: O(|s| log |t|).
Use bisect_left for the Follow-Up Binary Search
For the follow-up binary search, use bisect_left to find the first index >= current position in t. bisect_right would find the first index > current position, which would incorrectly skip a valid match when the character appears at exactly the current position. bisect_left returns the insertion point for the target value, ensuring you find the earliest valid match at or after the required position.