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 positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
Example 1:
Input: s = "abc", t = "ahbgdc" Output: true
Example 2:
Input: s = "axc", t = "ahbgdc" Output: false
Constraints:
0 <= s.length <= 1000 <= t.length <= 104s and t consist only of lowercase English letters.Follow up: Suppose there are lots of incoming
s, say s1, s2, ..., sk where k >= 109, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?The Two-Pointer Technique involves maintaining two indices, one for each string (s and t). Start both pointers at the beginning of their respective strings. Move the pointer for 's' only when there's a match with the current character at 't'. This ensures that all characters in 's' appear in 't' with the correct order. If the pointer for 's' reaches the end of 's', then 's' is a subsequence of 't'.
This C solution employs a while loop with two pointers to check each character. The loop advances through 't', incrementing a pointer for 's' only when characters match. If 's' is fully traversed (indexS == lengthS), it confirms 's' as a subsequence of 't'.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) where n is the length of 't'.
Space Complexity: O(1) as no additional data structures are used.
For frequent 's' queries, preprocess 't' to build a map of character positions using a dictionary or hashmap structure. This allows for efficient binary search to determine if 's' is a subsequence, as only relevant sections of 't' need to be checked.
This Python solution uses a map to store positions of each character in 't'. For each character in 's', it performs a binary search using the 'bisect' module to locate the next valid position in 't'. This avoids full scans and enhances efficiency for large numbers of 's'.
Preprocessing Time Complexity: O(n) for preparing the map where n is the length of 't'.
Checking Time Complexity: O(mlog(k)) for each 's', where m is the length of 's' and k is the average number of occurrences of each character in 't'.
Space Complexity: O(n) for the map storage.
| Approach | Complexity |
|---|---|
| Two-Pointer Technique | Time Complexity: O(n) where n is the length of 't'. |
| Follow-up: Using Preprocessing | Preprocessing Time Complexity: O(n) for preparing the map where n is the length of 't'. |
Is Subsequence - Leetcode 392 • NeetCode • 59,162 views views
Watch 9 more video solutions →Practice Is Subsequence with our built-in code editor and test cases.
Practice on FleetCode