Check if one string is a subsequence of another

Given two strings s and t, determine whether s is a subsequence of t.

A subsequence keeps relative order but does not require contiguous characters.

Input

• s : a string (may be empty)
• t : a string (may be empty)

Output

• Return true if s is a subsequence of t , otherwise return false .

Examples

• s = "abc" , t = "aabzc" → true (pick a at index 1, b at index 2, c at index 4)
• s = "axc" , t = "ahbgdc" → false

Constraints

• 0 ≤ |s|, |t| ≤ 10^5 (assume ASCII letters)

Follow-up (optional): If you need to answer this query for dozens of different s strings against the same t, what preprocessing (if any) would you do?