392. Is Subsequence
Model: qwen2.5-coder:14b
Topics: Binary Search,Dynamic Programming,Greedy
FAANG asked: 0
Acceptance rate: 49.6%
Problem Breakdown
The problem asks us to determine if string s is a subsequence of string t. A subsequence means that all characters of s appear in t in the same order, but not necessarily consecutively. The inputs are two strings, s and t, and the output should be a boolean indicating whether s is a subsequence of t.
Inputs:
s: A string that we want to check if it’s a subsequence.t: A string in which we want to find the subsequence.
Outputs:
- A boolean value (
trueorfalse) indicating whethersis a subsequence oft.
Implicit Constraints and Edge Cases:
- If
sis an empty string, it is trivially a subsequence of any stringt. - If
tis an empty string andsis not, thenscannot be a subsequence. - Both strings consist only of lowercase English letters.
Intuition
A brute-force approach would involve checking every possible substring of t to see if it matches s, which would be inefficient with high time complexity. Instead, we can use a two-pointer technique to traverse both strings simultaneously. This approach leverages the fact that we don’t need to find all subsequences but only check if one specific string is a subsequence.
The key insight is that we can iterate through t and try to match each character of s in order. If we can successfully match all characters of s while traversing t, then s is a subsequence of t.
Approach
We’ll use two pointers, one for each string:
- Initialize a pointer
ifor stringsstarting at 0. - Iterate through each character in string
tusing another pointerj. - If the current character in
tmatches the current character ins, move the pointerito the next character ins. - Continue this process until either all characters of
sare matched (ireaches the end ofs) or we finish traversingt. - If
ihas reached the end ofs, thensis a subsequence oft; otherwise, it is not.
Complexity Analysis
- Time Complexity: O(n), where n is the length of string
t. We traversetonce. - Space Complexity: O(1). We use only a constant amount of extra space for the pointers.
Solution
def isSubsequence(s: str, t: str) -> bool:
i, j = 0, 0
while i < len(s) and j < len(t):
if s[i] == t[j]:
i += 1
j += 1
return i == len(s)
Edge Cases Handled
- Empty
s: Ifsis empty, the function returnstruebecause an empty string is a subsequence of any string. - Empty
t: Iftis empty andsis not, the function returnsfalsebecause a non-empty string cannot be a subsequence of an empty string. - No matching characters: If no characters in
smatch the order int, the function correctly returnsfalse. - All characters match: If all characters in
sare found intin order, the function returnstrue.
This solution is efficient and straightforward, making it suitable for both small and large inputs.
Follow-up
If there are lots of incoming strings s1, s2, ..., sk where k >= 10^9, and you want to check one by one to see if t has its subsequence, we can preprocess string t to make the checks more efficient. One approach is to use binary search on a list of indices for each character in t. This preprocessing step would take O(n) time where n is the length of t, and each subsequent check for an s would take O(m log n) time, where m is the length of s. This way, we can handle a large number of queries efficiently.