Is Subsequence
EasyPrompt
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: trueExample 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Constraints:
0 <= s.length <= 1000 <= t.length <= 104sandtconsist 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?Approaches
3 approaches with complexity analysis and trade-offs.
This approach uses a 2D dynamic programming table to solve the problem. We define dp[i][j] as a boolean indicating if the first i characters of s form a subsequence of the first j characters of t. The table is filled based on a recurrence relation.
Algorithm
- Let
m = s.length()andn = t.length(). - Create a boolean DP table
dp[m+1][n+1]. - Initialize
dp[0][j] = truefor alljfrom 0 ton. - Iterate
ifrom 1 tom:- Iterate
jfrom 1 ton:- If
s.charAt(i-1) == t.charAt(j-1):dp[i][j] = dp[i-1][j-1]. - Else:
dp[i][j] = dp[i][j-1].
- If
- Iterate
- Return
dp[m][n].
Walkthrough
We create a DP table dp of size (s.length() + 1) x (t.length() + 1). dp[i][j] will be true if s.substring(0, i) is a subsequence of t.substring(0, j). The base case is that an empty string is a subsequence of any string, so the first row of the DP table is set to true. For the recurrence relation, if the characters s.charAt(i-1) and t.charAt(j-1) match, we need to check if the preceding substrings also formed a subsequence (dp[i-1][j-1]). If they don't match, we effectively ignore t.charAt(j-1) and check if s.substring(0, i) is a subsequence of t.substring(0, j-1) (dp[i][j-1]). The final answer is found in dp[s.length()][t.length()].
public boolean isSubsequence(String s, String t) { int m = s.length(); int n = t.length(); if (m == 0) { return true; } boolean[][] dp = new boolean[m + 1][n + 1]; for (int j = 0; j <= n; j++) { dp[0][j] = true; } for (int i = 1; i <= m; i++) { for (int j = 1; j <= n; j++) { if (s.charAt(i - 1) == t.charAt(j - 1)) { dp[i][j] = dp[i - 1][j - 1]; } else { dp[i][j] = dp[i][j - 1]; } } } return dp[m][n];}Complexity
Time
O(M * N), where M is the length of `s` and N is the length of `t`. We need to fill the entire M x N DP table.
Space
O(M * N) for the DP table, where M and N are the lengths of s and t. This can be optimized to O(N) since each row only depends on the previous row.
Trade-offs
Pros
A standard DP approach that is easy to understand for those familiar with dynamic programming.
Can be adapted to solve similar string problems.
Cons
Inefficient in both time and space compared to other solutions.
Not suitable for large strings due to high memory usage.
Solutions
Solution
''' >>> a=[1,2,3,1,2,3,1,2,3] >>> bisect.bisect_left(a, 2) 1 >>> bisect.bisect_right(a, 2) 8 ''' class Solution : def isSubsequence ( self , s : str , t : str ) -> bool : i , j , m , n = 0 , 0 , len ( s ), len ( t ) while i < m and j < n : if s [ i ] == t [ j ]: i += 1 j += 1 return i == m # follow up class Solution : def isSubsequence ( self , s : str , t : str ) -> bool : # pre-processing step index = defaultdict ( list ) for i , c in enumerate ( t ): index [ c ]. append ( i ) # iterate through each incoming string s j = 0 for c in s : if c not in index : return False pos_list = index [ c ] pos = bisect_left ( pos_list , j ) if pos == len ( pos_list ): return False j = pos_list [ pos ] + 1 return TrueVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.