Is Subsequence Check (Two Pointer)

Problem Statement

Given strings s and t, return true if s is a subsequence of t (the characters of s appear in t in the same order, not necessarily contiguous).

Example

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

Two Pointer Approach

Use one pointer for each string, both moving the same direction. Always advance the pointer on t; advance the pointer on s only when the characters match. If the s pointer reaches the end, every character was found in order.

Complexity

• Time: O(n)
• Space: O(1)

Solution Code

Python

def isSubsequence(s, t):
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

Java

boolean isSubsequence(String s, String t) {
    int i = 0;
    for (int j = 0; j < t.length() && i < s.length(); j++) {
        if (s.charAt(i) == t.charAt(j)) i++;
    }
    return i == s.length();
}

C++

bool isSubsequence(string s, string t) {
    int i = 0;
    for (int j = 0; j < (int)t.size() && i < (int)s.size(); j++) {
        if (s[i] == t[j]) i++;
    }
    return i == (int)s.size();
}

Key Takeaways

• Two pointers moving the same direction handle ordered matching.
• If s is exhausted, it is a subsequence.
• For many queries against the same t, precompute next-character indices.