Is Subsequence [Easy] — Two Pointer Greedy Match

Problem Statement

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

Input: s="ace", t="abcde" → true
Input: s="aec", t="abcde" → false

Intuition

Two pointers, one for s and one for t. Advance the s pointer only when characters match. If we reach the end of s, it's a subsequence.

Solutions

C

bool isSubsequence(char* s, char* t) {
    int i=0, j=0;
    while (s[i]&&t[j]) if(s[i]==t[j++]) i++;
    return s[i]=='�';
}

C++

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

Java

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++;
    return i==s.length();
}

JavaScript

var isSubsequence = function(s, t) {
    let i=0, j=0;
    while (i<s.length&&j<t.length) if(s[i]===t[j++]) i++;
    return i===s.length;
};

Python

def isSubsequence(s: str, t: str) -> bool:
    i = 0
    for c in t:
        if i < len(s) and c == s[i]:
            i += 1
    return i == len(s)

Complexity

Time: O(|t|)
Space: O(1)

Follow-up: 10^9 queries against same t

Precompute next[i][c] = next occurrence of character c at or after index i. Binary search on each character of s. O(|t| × 26) build, O(|s| log|t|) query.