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.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 goal of #392 Is Subsequence is to determine whether one string s appears as a subsequence inside another string t. A subsequence means the characters of s appear in the same order in t, but not necessarily contiguously.
The most efficient approach uses the Two Pointers technique. One pointer scans string s while the other scans t. Whenever matching characters are found, the pointer in s moves forward. If all characters of s are matched before reaching the end of t, then s is a valid subsequence. This greedy strategy works because the earliest valid matches always preserve the possibility of completing the subsequence.
For advanced scenarios, such as checking many different strings against the same t, a Dynamic Programming or preprocessing strategy can be used to store the next occurrence of characters. This helps answer multiple queries efficiently. The basic two-pointer solution runs in linear time with constant extra space.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers | O(n) | O(1) |
| DP / Preprocessed Next Occurrence | O(n + m) preprocessing, faster per query | O(n * alphabet) |
NeetCode
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'.
Time Complexity: O(n) where n is the length of 't'.
Space Complexity: O(1) as no additional data structures are used.
1#include <string>
2bool isSubsequence(const std::string &s, const std::string &t) {
3 int indexS = 0, indexT = 0;
4 while (indexS < s.size() && indexT < t.size()) {
5 if (s[indexS] == t[indexT]) {
6 indexS++;
7 }
8 indexT++;
9 }
10 return indexS == s.size();
11}This C++ solution mirrors the logic of the C solution. The language-specific syntax differences are implemented. It also maintains two pointers and increments them following the same rules of matching characters.
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.
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.
1from collections import defaultdict
2from bisect import bisect_right
3
4def
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of subsequence and string matching problems are common in FAANG-style interviews. They are used to test understanding of two pointers, greedy logic, and efficient string traversal techniques.
The optimal approach uses the two-pointer technique. One pointer scans the subsequence string while the other scans the main string and matches characters in order. This method works in linear time and requires constant extra space.
Yes, dynamic programming can be used, especially when handling many subsequence queries against the same string. By precomputing the next position of each character, you can quickly verify subsequences without rescanning the entire string each time.
The basic problem does not require complex data structures and can be solved using simple pointers on strings. For multiple queries, preprocessing with arrays or dynamic programming tables can help track the next occurrence of each character.
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'.