Given two strings s and t, return true if s is a subsequence of t. A subsequence is formed by deleting zero or more characters from t without changing the order of the rest, so "ace" is a subsequence of "abcde" but "aec" is not.
Example 1
Input: s = "abc", t = "ahbgdc"
Output: true
The letters a, b, c appear in
t in this order.Example 2
Input: s = "axc", t = "ahbgdc"
Output: false
There is no x in
t.Constraints
- 0 <= s.length <= 100
- 0 <= t.length <= 10^4
- Both strings contain only lowercase English letters
Hints
Frequently asked at: Google, Amazon, Paytm, Zoho
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
Generating subsequences of t is exponential. Instead, match greedily: scan t left to right and match the next needed character of s as early as possible. Matching early never hurts, because it leaves the most of t for the remaining characters. Two pointers do this in one pass.
Algorithm
- Set
i = 0as the pointer intos. - For each character
cint: ifi < len(s)ands[i] == c, increasei. - Return
i == len(s).
Time:
O(|t|)Space: O(1)Interview tip: Follow-up: many strings
s must be checked against the same huge t. Precompute, for each letter, the sorted list of its positions in t, then binary search for the next position, giving O(|s| log |t|) per query.class Solution: def isSubsequence(self, s: str, t: str) -> bool: i = 0 # next character of s we need for c in t: if i < len(s) and s[i] == c: i += 1 return i == len(s)Ctrl + Enter runs the examples