Is Subsequence

Approach

A subsequence of a string is a new string generated by deleting some (or no) characters from the original string without changing the relative order of the remaining characters. To check if s is a subsequence of t, we can use a Two Pointers approach. We place one pointer at the start of s and another at the start of t. We scan through t seeking the character that matches the current character in s.

If they match, we advance both pointers (we found a letter of s in t).
If they don’t match, we only advance the pointer in t (keep searching t). If we successfully advance the pointer for s entirely through the string s, it means all characters of s were found in t in the correct order.

Code

Optimal Approach (Brute force is identical conceptually)

// Pseudocode:
// i = 0 (pointer for s)
// j = 0 (pointer for t)
// While i < s.size() and j < t.size():
//   If s[i] == t[j]:
//       i += 1
//   j += 1
// Return True if i == s.size() else False
 
#include <string>
 
class Solution {
public:
    bool isSubsequence(std::string s, std::string t) {
        int i = 0, j = 0;
        
        while (i < s.size() && j < t.size()) {
            // If characters match, advance pointer for s
            if (s[i] == t[j]) {
                i++;
            }
            // Always advance pointer for t
            j++;
        }
            
        // If we successfully traversed all of s, it's a subsequence
        return i == s.size();
    }
};

Complexity

Time Complexity: O(T) where T is the length of string t. In the worst-case scenario, we iterate through the entirety of t.
Space Complexity: O(1). Only two integer pointers (i and j) are used.

Edge Cases

s is empty (s = ""): An empty string is mathematically a subsequence of any string. The loop condition i < s.size() immediately fails (0 < 0 is False), and it returns i == s.size() (0 == 0 → True). Correct.
t is empty (t = "", s = "a"): The loop won’t execute, returns 0 == 1 → False. Correct.
s is identical to t: Both pointers advance together perfectly, returning True.
s is longer than t: The loop will terminate when j exhausts t. i will naturally be less than s.size(), returning False.

Notes

Recognition: Checking relative ordering constraints without contiguity implies a Two-Pointer linear scan.
Follow-up Question handling: What if 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?
- If t is huge and we check many s strings, linear scan O(T) per string is too slow.
- Instead, pre-process t: Create a hash map mapping each character to a sorted list of its indices in t.
- Then, for each s, iterate through its characters and use Binary Search (std::upper_bound) on the list of indices to find the next valid index in t. This reduces checking each s to O(len(s) * log(T)).

Is Subsequence

published

modified

length

source