Is Subsequence
Determine if s is a subsequence of t using a single greedy two-pointer walk.
2 min read
two-pointers string
Problem#
Return true if s is a subsequence of t — i.e., s can be formed by deleting zero or more characters from t without reordering.
Examples#
s = "abc", t = "ahbgdc"→trues = "axc", t = "ahbgdc"→false
Constraints#
0 <= s.length <= 100,0 <= t.length <= 10^4.
Approach#
Walk both with two pointers; advance i over s only on match, advance j over t every step. Subsequence iff i reaches the end of s.
Solution#
class Solution {public: bool isSubsequence(string s, string t) { int i = 0; for (char c : t) { if (i < (int)s.size() && s[i] == c) ++i; } return i == (int)s.size(); }};func isSubsequence(s string, t string) bool { i := 0 for j := 0; j < len(t); j++ { if i < len(s) && s[i] == t[j] { i++ } } return i == len(s)}class Solution: def isSubsequence(self, s: str, t: str) -> bool: i = 0 for c in t: if i < len(s) and s[i] == c: i += 1 return i == len(s)function isSubsequence(s, t) { let i = 0; for (const c of t) { if (i < s.length && s[i] === c) i++; } return i === s.length;}class Solution { public boolean isSubsequence(String s, String t) { int i = 0; for (int j = 0; j < t.length(); j++) { if (i < s.length() && s.charAt(i) == t.charAt(j)) i++; } return i == s.length(); }}function isSubsequence(s: string, t: string): boolean { let i = 0; for (const c of t) { if (i < s.length && s[i] === c) i++; } return i === s.length;}Editorial#
Greedy is optimal here: a deferred match in t never helps. The early-exit version (returning true as soon as i == s.size()) is a constant-factor speedup but doesn’t change asymptotics. For the follow-up where many s values are checked against the same t, precomputing per-character next-occurrence arrays drops each query to O(|s| log |t|).
Complexity#
- Time: O(|t|).
- Space: O(1).
Concept revision#
Related#