Is Subsequence
Is Subsequence is a easy arrays & hashing problem solved with the two pointer pattern.
The best approach, optimal (two pointers, greedy match), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (longest common subsequence dp) up.
Problem
Given two strings s and t, return true if s is a subsequence of t, and false otherwise.
A subsequence is what you get by deleting zero or more characters from a string without changing the order of the characters that remain. For example, "art" is a subsequence of "party", but "tra" is not.
Examples
Example 1
- Input
s = "rope", t = "marooned"- Output
false- Why
- 'r' and 'o' can be matched, but t has no 'p' after them, so the letters of s cannot all be found in order.
Example 2
- Input
s = "tin", t = "strain"- Output
true- Why
- Pick the 't' at index 1, the 'i' at index 4 and the 'n' at index 5.
Example 3
- Input
s = "", t = "anything"- Output
true- Why
- The empty string is a subsequence of every string.
Constraints
0 <= s.length <= 1000 <= t.length <= 10^4sandtconsist only of lowercase English letters
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (longest common subsequence DP) | O(m · n) | O(m · n) |
| Optimal (two pointers, greedy match) | O(n) | O(1) |
1Brute force (longest common subsequence DP)
O(m · n)Every cell of the table is filled once.O(m · n)The full table is stored.s is a subsequence of t exactly when the longest common subsequence of s and t has length |s|. Fill the classic LCS table and compare.
- Create a table dp of size (m + 1) x (n + 1) where m = |s|, n = |t|.
- dp[i][j] = dp[i-1][j-1] + 1 if s[i-1] == t[j-1], else max(dp[i-1][j], dp[i][j-1]).
- Return dp[m][n] == m.
class Solution {
public boolean isSubsequence(String s, String t) {
int m = s.length(), n = t.length();
int[][] dp = new int[m + 1][n + 1];
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] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n] == m;
}
}class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s[i - 1] == t[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
return dp[m][n] == mclass Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size(), n = t.size();
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s[i - 1] == t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n] == m;
}
};function isSubsequence(s, t) {
const m = s.length, n = t.length;
const dp = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (s[i - 1] === t[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;
else dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m][n] === m;
}2Optimal (two pointers, greedy match)
O(n)t is scanned once.O(1)Only one index.Scan t from left to right with a pointer i into s. Whenever t[j] equals s[i], match it and move i forward. Taking the earliest possible match never hurts, because it leaves the most of t for the remaining letters. s is a subsequence if i reaches the end of s.
- Set i = 0.
- For each character c of t: if i < |s| and c == s[i], increment i.
- Return i == |s|.
class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0;
for (int j = 0; j < t.length() && i < s.length(); j++) {
if (s.charAt(i) == t.charAt(j)) i++;
}
return i == s.length();
}
}class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = 0
for c in t:
if i < len(s) and s[i] == c:
i += 1
return i == len(s)class Solution {
public:
bool isSubsequence(string s, string t) {
size_t i = 0;
for (size_t j = 0; j < t.size() && i < s.size(); j++) {
if (s[i] == t[j]) i++;
}
return i == s.size();
}
};function isSubsequence(s, t) {
let i = 0;
for (let j = 0; j < t.length && i < s.length; j++) {
if (s[i] === t[j]) i++;
}
return i === s.length;
}Edge cases to test
- s is empty (always true)
- t is empty and s is not (false)
- s equals t
- s is longer than t
- Repeated letters in s that need separate occurrences in t, like s = "aa", t = "ab"
Hints
Hint 1
Is it ever a mistake to match the current letter of s with its earliest possible position in t?
Hint 2
Walk through t once with a pointer into s; advance the s pointer whenever the letters match.
FAQ
What is the best time complexity for Is Subsequence?
Optimal (two pointers, greedy match) runs in O(n) time and O(1) extra space. t is scanned once.
Which pattern does Is Subsequence use?
It is a arrays & hashing problem that uses the two pointer pattern. Other problems with the same pattern: Two Sum II - Input Array Is Sorted, Valid Triangle Number, Container With Most Water.
Is there a brute force solution for Is Subsequence?
Yes. Brute force (longest common subsequence DP) takes O(m · n) time and O(m · n) space. s is a subsequence of t exactly when the longest common subsequence of s and t has length |s|.
Which edge cases should I test for Is Subsequence?
s is empty (always true); t is empty and s is not (false); s equals t; s is longer than t; Repeated letters in s that need separate occurrences in t, like s = "aa", t = "ab".