Is Subsequence(#392)
Category: String, Two Pointer
🧩 Problem Statement
Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence of a string is a new string formed by deleting some (or no) characters from the original string, without disturbing the relative order of the remaining characters.
📚 Examples
Input: s = "abc", t = "ahbgdc"
Output: true
Input: s = "axc", t = "ahbgdc"
Output: false
Input: s = "ace", t = "abcde"
Output: true
🧠 Approach
We use the **Two Pointer Technique** to efficiently traverse both strings:
• Initialize two pointers: `sIndex` for string **s** and `tIndex` for string **t**.
• Loop through string **t**:
- If `s[sIndex] === t[tIndex]`, move both pointers forward (we found a match).
- Otherwise, move only `tIndex`.
• If we reach the end of string **s**, that means all characters of **s** were found in order inside **t**. So, **s** is a subsequence of **t**.
This approach works in **O(n)** time with **O(1)** space.
💻 Code
var isSubsequence = function(s, t) {
let sIndex = 0;
let tIndex = 0;
while (tIndex < t.length) {
if (s[sIndex] === t[tIndex]) {
sIndex++;
}
tIndex++;
}
return sIndex === s.length;
};
console.log(isSubsequence("abc", "ahbgdc")); // true
console.log(isSubsequence("axc", "ahbgdc")); // false📈 Complexity
Time: O(n), where n is the length of string t
Space: O(1), using just two pointers