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.
This is a greedy and efficient approach that uses two pointers to iterate through the strings s and t. One pointer tracks the current character to be found in s, and the other scans t to find that character.
Algorithm
- Initialize two pointers,
i = 0forsandj = 0fort. - Loop while
i < s.length()andj < t.length():- If
s.charAt(i) == t.charAt(j), incrementi. - Always increment
j.
- If
- After the loop, if
i == s.length(), returntrue. Otherwise, returnfalse.
Walkthrough
We use two pointers, i for string s and j for string t. We iterate through t with pointer j. Whenever we find a character t.charAt(j) that matches the character s.charAt(i), we advance the pointer i to look for the next character in s. We always advance the pointer j to scan through t. If we have advanced i to be equal to the length of s, it means all characters of s have been found in t in the correct order.
public boolean isSubsequence(String s, String t) { int i = 0; // pointer for s int j = 0; // pointer for t while (i < s.length() && j < t.length()) { if (s.charAt(i) == t.charAt(j)) { i++; } j++; } return i == s.length();}Complexity
Time
O(N), where N is the length of `t`. We iterate through `t` at most once.
Space
O(1), as we only use a constant amount of extra space for the pointers.
Trade-offs
Pros
Very efficient in both time and space.
Simple and intuitive to implement.
Cons
For the follow-up scenario with many
squeries on the samet, this approach re-scanstevery time, which is suboptimal.
This approach is designed for the follow-up scenario where we check many s strings against a single t. It involves pre-processing t to map each character to a list of its indices. Then, for each s, we can efficiently find the required characters using binary search.
Algorithm
- Pre-computation:
- Create a map
charIndiceswhere keys are characters and values are lists of their indices int. - Iterate through
tand populate this map.
- Create a map
- Query for
s:- Initialize
last_match_index = -1. - For each character
cins:- Get the list of indices for
cfromcharIndices. If not found, returnfalse. - Binary search this list to find the smallest index
idxsuch thatidx > last_match_index. - If no such index is found, return
false. - Update
last_match_index = idx.
- Get the list of indices for
- If the loop completes, return
true.
- Initialize
Walkthrough
This method is ideal for the follow-up problem. First, we pre-process t by creating a hash map where keys are characters and values are sorted lists of their indices in t. This takes O(|t|) time. Then, to check if a string s is a subsequence, we iterate through s. For each character, we use binary search on its corresponding index list to find the next available occurrence in t (i.e., an index greater than the index of the previous match). If we find a valid index for every character in s, it is a subsequence.
// This implementation is for the follow-up scenario.// For a single call, the two-pointer approach is better.public boolean isSubsequence(String s, String t) { // Pre-computation part Map<Character, List<Integer>> charIndices = new HashMap<>(); for (int i = 0; i < t.length(); i++) { char c = t.charAt(i); charIndices.computeIfAbsent(c, k -> new ArrayList<>()).add(i); } // Query part int prevMatchIndex = -1; for (char c : s.toCharArray()) { List<Integer> indices = charIndices.get(c); if (indices == null) { return false; } int nextMatchIndex = findNextIndex(indices, prevMatchIndex); if (nextMatchIndex == -1) { return false; } prevMatchIndex = nextMatchIndex; } return true;} // Helper function to find the smallest index > prevMatchIndexprivate int findNextIndex(List<Integer> indices, int prevMatchIndex) { int left = 0; int right = indices.size() - 1; int result = -1; while (left <= right) { int mid = left + (right - left) / 2; if (indices.get(mid) > prevMatchIndex) { result = indices.get(mid); right = mid - 1; // Try to find an even smaller index } else { left = mid + 1; } } return result;}Complexity
Time
O(N + K * M * log(N)), where N=|t|, M=|s|, and K is the number of queries. O(N) for one-time pre-computation. Each query takes O(M * log(N)).
Space
O(N), where N is the length of `t`. This is for storing the character indices map. The total number of indices stored across all lists is N.
Trade-offs
Pros
Highly efficient for the scenario with many queries on a fixed
t.The expensive pre-computation is done only once.
Cons
Higher overhead for a single query compared to the two-pointer approach.
Uses more memory to store the index map.
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 Truepublic class Solution { public bool IsSubsequence(string s, string t) { int m = s.Length, n = t.Length; int i = 0, j = 0; for (; i < m && j < n; ++j) { if (s[i] == t[j]) { ++i; } } return i == m; }}import java.util.ArrayList ; import java.util.HashMap ; import java.util.List ; import java.util.Map ; public class Is_Subsequence { class Solution { public boolean isSubsequence ( String s , String t ) { if ( s == null || s . length () == 0 ) { return true ; } int i = 0 ; for ( int j = 0 ; j < t . length (); j ++) { if ( s . charAt ( i ) == t . charAt ( j )) { i ++; if ( i == s . length ()) { // last char is matched return true ; } } } return false ; } } class Solution_followup { public boolean isSubsequence ( String s , String t ) { // step 1: save all the index for the t Map < Character , List < Integer >> map = new HashMap <>(); for ( int i = 0 ; i < t . length (); i ++) { char c = t . charAt ( i ); if (! map . containsKey ( c )) { List < Integer > pos = new ArrayList <>(); pos . add ( i ); map . put ( c , pos ); } else { List < Integer > pos = map . get ( c ); pos . add ( i ); // map.put(c, pos); } } // step 2: for each char in s, find the first index int prevIndex = - 1 ; for ( int i = 0 ; i < s . length (); i ++) { char c = s . charAt ( i ); List < Integer > pos = map . get ( c ); if ( pos == null || pos . size () == 0 ) { return false ; } int currentIndex = getNextIndexGreaterThanTarget ( pos , prevIndex ); if ( currentIndex == - 1 ) { return false ; } prevIndex = currentIndex ; } return true ; } // find next number greater than target // if not found, return -1 private int getNextIndexGreaterThanTarget ( List < Integer > pos , int targetIndex ) { int lo = 0 ; int hi = pos . size () - 1 ; while ( lo + 1 <= hi ) { int mid = lo + ( hi - lo ) / 2 ; if ( pos . get ( mid ) == targetIndex ) { lo = mid + 1 ; } else if ( pos . get ( mid ) > targetIndex ) { hi = mid ; } else if ( pos . get ( mid ) < targetIndex ) { lo = mid + 1 ; } } if ( pos . get ( lo ) > targetIndex ) { return pos . get ( lo ); } if ( pos . get ( hi ) > targetIndex ) { return pos . get ( hi ); } return - 1 ; } } } ////// class Solution { public boolean isSubsequence ( String s , String t ) { int m = s . length (), n = t . length (); int i = 0 , j = 0 ; while ( i < m && j < n ) { if ( s . charAt ( i ) == t . charAt ( j )) { ++ i ; } ++ j ; } return i == m ; } }// OJ: https://leetcode.com/problems/is-subsequence/ // Time: O(M + N) // Space: O(1) class Solution { public: bool isSubsequence ( string s , string t ) { int i = 0 , j = 0 , M = s . size (), N = t . size (); for (; i < M && j < N ; ++ j ) { if ( s [ i ] == t [ j ]) ++ i ; } return i == M ; } };Video 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.