1. Understanding 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 from the original string by deleting some (or no) characters without changing the relative order of the remaining characters. (For example, "ace" is a subsequence of "abcde" while "aec" is not).

Key Distinction (Subsequence vs. Substring):

Unlike a substring, a subsequence does not require characters to be contiguous in the target string. They only need to appear in the same relative order from left to right.

The Interview Follow-Up Twist:

What if there are lots of incoming s strings, say s1, s2, ..., sk where k >= 1 billion, and you want to check one by one against a single, massive, unchanging string t?

2. The Naive Approach: Generating All Subsequences

The most basic approach would be to recursively generate all possible subsequences of string t and check if s exists within that generated set.

Trade-off Analysis

• Time Complexity: O(2^N) where N is the length of t — Exponential time, which will immediately result in a Time Limit Exceeded (TLE) error even for modest string lengths.
• Space Complexity: O(2^N) — Storing every generated string consumes massive memory.

3. The Optimal Approach: Two-Pointer Greedy Matching (O(N) Time)

Because relative order is strictly preserved, we can make a greedy choice: whenever we find a character in t that matches our target character in s, we should match it immediately and move on to the next target character in s.

We maintain two pointers:

• i tracking our current search position in s.
• j scanning through the target string t.

By traversing string t once, if pointer i successfully reaches the end of string s, then all characters of s were matched in sequence!

4. The Logic Step-by-Step

1. Initialize pointer i = 0 (for string s) and pointer j = 0 (for string t).
2. Traverse String t: Loop while i < len(s) and j < len(t):
   • If s[i] == t[j], increment i by 1 to look for the next required character.
   • Always increment j by 1 on every iteration to keep scanning through t.
3. Evaluate Result: If i == len(s), we found every character of s in order. Return true. Otherwise, return false.

Addressing the Follow-Up Scenario:

If string t is fixed and we have billions of queries for s, doing an O(N) scan per query is too slow. Instead, we can pre-process t into a Hash Map storing the indices of each character (e.g., {'a': [0, 5], 'b': [2, 8]}). For each character in s, we can use Binary Search (std::upper_bound / bisect) to quickly find the next available index in O(log N) time per character!

5. Complexity Analysis

• Time Complexity: O(N) — Where N is the length of string t. We traverse string t at most once.
• Space Complexity: O(1) — We only store two scalar pointer variables (i and j), requiring constant memory.

6. Code Implementations

Expand the sections below to see the optimal O(1) space Two-Pointer implementations across different languages.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0
        len_s, len_t = len(s), len(t)
        
        while i < len_s and j < len_t:
            # If characters match, advance pointer in s
            if s[i] == t[j]:
                i += 1
            # Always advance pointer in t
            j += 1
            
        # If i reached the end of s, all characters were found in order
        return i == len_s

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        int j = 0;
        int lenS = s.length();
        int lenT = t.length();
        
        while (i < lenS && j < lenT) {
            // Match found, advance pointer for s
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            // Always advance pointer for t
            j++;
        }
        
        return i == lenS;
    }
}

#include <string>

class Solution {
public:
    bool isSubsequence(std::string s, std::string t) {
        int i = 0;
        int j = 0;
        int lenS = s.length();
        int lenT = t.length();
        
        while (i < lenS && j < lenT) {
            // Match found, advance pointer for s
            if (s[i] == t[j]) {
                i++;
            }
            // Always advance pointer for t
            j++;
        }
        
        return i == lenS;
    }
};

7. Conclusion: You Are Ready

Congratulations! You have mastered the Two-Pointer strategy for checking subsequences. By recognizing that early greedy matching preserves optimal opportunities for future characters, you reduced an exponential search space down to a single linear pass in O(1) extra space. Understanding how two-pointer traversals operate is a critical building block for string matching, long common subsequences, and two-pointer array algorithms. Keep building your toolkit and keep coding!