Is Subsequence

Is Subsequence

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 that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative order of the remaining characters. For example, "ace" is a subsequence of "abcde" while "aec" is not.

Examples

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true
Explanation: 'a' is found at index 0, 'b' at index 2, 'c' at index 5 in t.

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: After finding 'a' at index 0, there is no 'x' in the remaining part of t.

Example 3:

Input: s = "", t = "ahbgdc"
Output: true
Explanation: An empty string is a subsequence of any string.

Constraints

• 0 <= s.length <= 100
• 0 <= t.length <= 10^4
• s and t consist only of lowercase English letters.

Expected Complexity

• Time: O(n) where n is the length of t
• Space: O(1)