Back to solutions

Is Subsequence

EasyArrays

Check whether s is a subsequence of t.

Open problem
Constraints
  • 0 <= |s| <= 100
  • 0 <= |t| <= 10^4

Two pointers

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

Keep a pointer i into s. Scan t once; whenever the current character of t matches s[i], advance i. If i reaches the end of s, every character of s was matched in order, so s is a subsequence.

Key terms
subsequence:
A sequence formed by deleting zero or more characters without reordering the rest.
two pointers:
Advancing one index through s and another through t to compare them in a single pass.
bool isSubsequence(const string& s, const string& t) {
    size_t i = 0;
    for (char c : t) if (i < s.size() && s[i] == c) i++;
    return i == s.size();
}
Step by step
  1. Set i = 0 pointing at the first needed character of s.
  2. Walk through every character c of t.
  3. If i is still within s and s[i] == c, advance i (this character is matched).
  4. After scanning t, s is a subsequence exactly when i reached len(s).