#392 - Is Subsequence

EasyTwo Pointers

Given two strings s and t, return true if s is a subsequence of t, i.e. s can be obtained by deleting some (or no) characters from t without changing the order of the remaining characters.

Input	Output
s = "abc", t = "ahbgdc"	true
s = "axc", t = "ahbgdc"	false
s = "", t = "ahbgdc"	true

Solution Space

Try it

/**
 * Checks whether s is a subsequence of t using two pointers.
 *
 * @param s The candidate subsequence
 * @param t The source string to match against
 * @returns true if s is a subsequence of t
 */
export function isSubsequence(s: string, t: string): boolean {
  let si = 0;

  for (let ti = 0; ti < t.length && si < s.length; ti++) {
    if (s[si] === t[ti]) si++;
  }

  return si === s.length;
}

Approach: two pointers – use one pointer for each string, advancing the subsequence pointer only when characters match.

Time: O(n) – where n = `t.length`; each character of `t` is visited at most once.

Space: O(1) – only two index variables.

Alternative approaches:

Approach	Idea	Time	Space
Binary search (follow-up)	Pre-process t into a map of char → sorted list of indices, then for each char in s binary-search for the next valid index. Useful when checking many s strings against the same t.	O(m log n) per query after O(n) pre-processing	O(n)

Why the two-pointer method is preferred:

• Simplest to implement with optimal O(n) time for a single query.
• The binary-search variant only pays off when there are many s strings to validate against the same t (the LeetCode follow-up scenario).

#283 Move Zeroes

#1679 Max Number of K-Sum Pairs