Is Subsequence
Description
You get two strings, s and t. Return true if s is a subsequence of t, and false otherwise.
A subsequence is what's left after deleting some letters of t (possibly none) without changing the order of the rest. "ace" is a subsequence of "abcde"; "aec" isn't, because in "abcde" the e comes after the c.
Follow-up: what if a huge number of strings s1, s2, …, sk (k ≥ 10^9) are checked against the same t, one after another? How would you change your solution?
Examples
Example 1
Input: s = "abc", t = "ahbgdc"
Output: true
Explanation: a, b and c appear in t in that order: a at position 0, b at 2, c at 5. So s is a subsequence: true.
Example 2
Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: There's no x anywhere in t, so s can't be made from it: false.
Example 3
Input: s = "", t = "abc"
Output: true
Explanation: An empty s needs nothing from t. It's a subsequence of every string, even an empty one: true.
Constraints
- 0 ≤ s.length ≤ 100
- 0 ≤ t.length ≤ 10^4
- s and t consist only of lowercase English letters
Editorial
Brute Force
Intuition
Without any insight, the question splits into smaller ones: do the first i letters of s fit in the first j letters of t? Call the answer fits[i][j].
Look at the last letter of that prefix of t. You can always ignore it, so if the first i letters of s already fit in the first j - 1 letters, they fit in j. And if it equals s's i-th letter, you can use it to match that letter, as long as the first i - 1 letters fit in the first j - 1. Fill a table with every pair, and the bottom-right cell is the answer.
Step-by-Step Explanation
Let's fill the table for s = "abc", t = "ahbgdc" (1 means yes):
- Row 0 is all 1s: the empty string fits in every prefix of t.
- Column 0 is 0 below that: a non-empty s can't fit in an empty t.
- Every other cell is
fits[i][j - 1] or (s[i - 1] == t[j - 1] and fits[i - 1][j - 1]). - The bottom-right cell, fits[3][6], is 1: true.
That's 28 cells for one small check.
Fill Every Prefix Pair — Each cell asks whether the first i letters of s fit in the first j letters of t; it copies the cell to its left, or uses the diagonal when the letters match.
Algorithm
- Make a table
fitsof size (m + 1) × (n + 1), all false. - Set
fits[0][j] = truefor everyj. - For
ifrom 1 to m andjfrom 1 to n:fits[i][j] = fits[i][j - 1] or (s[i - 1] == t[j - 1] and fits[i - 1][j - 1]). - Return
fits[m][n].
Code
class Solution {
public:
bool isSubsequence(string s, string t) {
int m = s.size(), n = t.size();
// fits[i][j]: are the first i letters of s a subsequence of the first j letters of t?
vector<vector<bool>> fits(m + 1, vector<bool>(n + 1, false));
for (int j = 0; j <= n; j++) fits[0][j] = true; // the empty string fits anywhere
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// skip t's j-th letter, or use it to match s's i-th letter
fits[i][j] = fits[i][j - 1] || (s[i - 1] == t[j - 1] && fits[i - 1][j - 1]);
}
}
return fits[m][n];
}
};
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
m, n = len(s), len(t)
# fits[i][j]: are the first i letters of s a subsequence of the first j letters of t?
fits = [[False] * (n + 1) for _ in range(m + 1)]
for j in range(n + 1):
fits[0][j] = True # the empty string fits anywhere
for i in range(1, m + 1):
for j in range(1, n + 1):
# skip t's j-th letter, or use it to match s's i-th letter
fits[i][j] = fits[i][j - 1] or (s[i - 1] == t[j - 1] and fits[i - 1][j - 1])
return fits[m][n]
class Solution {
public boolean isSubsequence(String s, String t) {
int m = s.length(), n = t.length();
// fits[i][j]: are the first i letters of s a subsequence of the first j letters of t?
boolean[][] fits = new boolean[m + 1][n + 1];
for (int j = 0; j <= n; j++) fits[0][j] = true; // the empty string fits anywhere
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
// skip t's j-th letter, or use it to match s's i-th letter
fits[i][j] = fits[i][j - 1] || (s.charAt(i - 1) == t.charAt(j - 1) && fits[i - 1][j - 1]);
}
}
return fits[m][n];
}
}
var isSubsequence = function(s, t) {
const m = s.length, n = t.length;
// fits[i][j]: are the first i letters of s a subsequence of the first j letters of t?
const fits = Array.from({ length: m + 1 }, () => new Array(n + 1).fill(false));
for (let j = 0; j <= n; j++) fits[0][j] = true; // the empty string fits anywhere
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
// skip t's j-th letter, or use it to match s's i-th letter
fits[i][j] = fits[i][j - 1] || (s[i - 1] === t[j - 1] && fits[i - 1][j - 1]);
}
}
return fits[m][n];
};
Complexity Analysis
Time Complexity: O(m · n)
One step per cell: up to 101 × 10,001, about a million, for one check.
Space Complexity: O(m · n)
The table itself. (Keeping only the previous row brings it down to O(n), but the time stays the same.)
Why This Approach Is Not Efficient
A million steps per check is fine once. The follow-up asks for a billion checks against the same t, and then it's a billion million.
More to the point, most of the table is wasted. When a letter of t matches the next letter of s, there's no reason to ever skip it: matching each letter of s at its earliest possible place leaves the most of t for the letters after it, and waiting for a later copy leaves less room, never more. So one walk through t decides it, with no table at all.
Optimal Approach - Two Pointers
Intuition
Put one pointer in each string. j walks through t, one letter at a time. i points at the next letter of s you still need, and it moves only when t[j] matches it.
Taking the earliest match is always safe: it never uses up a letter that a later letter of s needed, because that later letter has to come after this one anyway. If i reaches the end of s, every letter was found, in order.
Step-by-Step Explanation
Let's trace s = "abc", t = "ahbgdc":
- j = 0: t[0] = 'a' matches s[0], so take it. i = 1.
- j = 1: t[1] = 'h' isn't s[1] = 'b'. Skip it.
- j = 2: t[2] = 'b' matches s[1], so take it. i = 2.
- j = 3: t[3] = 'g' isn't s[2] = 'c'. Skip it.
- j = 4: t[4] = 'd' isn't s[2] = 'c'. Skip it.
- j = 5: t[5] = 'c' matches s[2], so take it. i = 3.
i reached the end of s, so the answer is true.
One Pointer in Each String — j walks t; i moves along s only when t[j] matches s[i]. Green letters are matched.
Algorithm
- Set
i = 0andj = 0. - While
i < len(s)andj < len(t):- if
s[i] == t[j], add 1 toi; - add 1 to
j.
- if
- Return whether
i == len(s).
Code
class Solution {
public:
bool isSubsequence(string s, string t) {
int i = 0, j = 0;
while (i < (int)s.size() && j < (int)t.size()) {
if (s[i] == t[j]) i++; // found: now look for the next letter of s
j++; // t's pointer moves every step
}
return i == (int)s.size(); // every letter of s was found, in order
}
};
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
i = j = 0
while i < len(s) and j < len(t):
if s[i] == t[j]: # found: now look for the next letter of s
i += 1
j += 1 # t's pointer moves every step
return i == len(s) # every letter of s was found, in order
class Solution {
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) i++; // found: now look for the next letter of s
j++; // t's pointer moves every step
}
return i == s.length(); // every letter of s was found, in order
}
}
var isSubsequence = function(s, t) {
let i = 0, j = 0;
while (i < s.length && j < t.length) {
if (s[i] === t[j]) i++; // found: now look for the next letter of s
j++; // t's pointer moves every step
}
return i === s.length; // every letter of s was found, in order
};
Complexity Analysis
Time Complexity: O(n)
j visits each letter of t at most once, and every step does one comparison.
Space Complexity: O(1)
Two integers.
Follow-Up - Many Strings Against the Same t
Intuition
With a billion strings s against one t, walking t again for each of them costs O(n) every time. Pay for t once instead: list, for every letter, the positions where it appears in t. Those lists are sorted, because they're built left to right.
Then check each s by jumping: for its next letter, binary search that letter's list for the first position at or after pos (the place just past the previous match). If there is none, the answer is false. That's the same earliest-match rule as the two pointers, without walking the letters in between.
Code
class Solution {
public:
bool isSubsequence(string s, string t) {
// where[c]: the positions of letter c in t, in order. Build it once per t; reuse it for every s.
vector<int> where[26];
for (int j = 0; j < (int)t.size(); j++) where[t[j] - 'a'].push_back(j);
int pos = 0; // the first position of t still free to use
for (char ch : s) {
const vector<int>& spots = where[ch - 'a'];
auto it = lower_bound(spots.begin(), spots.end(), pos); // the first copy of ch at or after pos
if (it == spots.end()) return false;
pos = *it + 1;
}
return true;
}
};
from bisect import bisect_left
from collections import defaultdict
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
# where[c]: the positions of letter c in t, in order. Build it once per t; reuse it for every s.
where = defaultdict(list)
for j, ch in enumerate(t):
where[ch].append(j)
pos = 0 # the first position of t still free to use
for ch in s:
spots = where[ch]
k = bisect_left(spots, pos) # the first copy of ch at or after pos
if k == len(spots):
return False
pos = spots[k] + 1
return True
class Solution {
public boolean isSubsequence(String s, String t) {
// where[c]: the positions of letter c in t, in order. Build it once per t; reuse it for every s.
List<List<Integer>> where = new ArrayList<>();
for (int c = 0; c < 26; c++) where.add(new ArrayList<>());
for (int j = 0; j < t.length(); j++) where.get(t.charAt(j) - 'a').add(j);
int pos = 0; // the first position of t still free to use
for (char ch : s.toCharArray()) {
List<Integer> spots = where.get(ch - 'a');
int lo = 0, hi = spots.size(); // the first copy of ch at or after pos
while (lo < hi) {
int mid = (lo + hi) / 2;
if (spots.get(mid) < pos) lo = mid + 1; else hi = mid;
}
if (lo == spots.size()) return false;
pos = spots.get(lo) + 1;
}
return true;
}
}
var isSubsequence = function(s, t) {
// where[c]: the positions of letter c in t, in order. Build it once per t; reuse it for every s.
const where = new Map();
for (let j = 0; j < t.length; j++) {
if (!where.has(t[j])) where.set(t[j], []);
where.get(t[j]).push(j);
}
let pos = 0; // the first position of t still free to use
for (const ch of s) {
const spots = where.get(ch) || [];
let lo = 0, hi = spots.length; // the first copy of ch at or after pos
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (spots[mid] < pos) lo = mid + 1; else hi = mid;
}
if (lo === spots.length) return false;
pos = spots[lo] + 1;
}
return true;
};
Complexity Analysis
Time Complexity: O(n) once to build the lists, then O(m log n) per string s.
Space Complexity: O(n) for the lists.
The code above builds the lists inside the function so it runs as a normal solution; with many queries you build them once and keep them. A table of "the next position of each letter after every seat" makes each step O(1) instead, at 26 × n entries of memory.
Common Mistakes
Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.
Counting letters instead of keeping their order. return all(have[c] >= k for c, k in need.items())
On s = "ab", t = "ba" it returns true; the answer is false. Having enough of each letter isn't enough: a subsequence keeps the letters in order. Counting says "ab" fits in "ba", but there the b comes first.
Searching again from the last match. pos = t.find(ch, pos)
On s = "aa", t = "a" it returns true; the answer is false. t.find(ch, pos) starts at the position of the last match, so the same letter of t can be matched twice. The next search has to start one past it: pos + 1.
Returning false when t is empty. if not t: return False
On s = "", t = "" it returns false; the answer is true. An empty t can still contain an empty s: deleting nothing from "" gives "". The shortcut if not t: return False is only right when s isn't empty.
Where This Pattern Is Taught
This problem practises two pointers on two inputs, one pointer each, where one pointer waits for a match. It's taught in Two Pointers on Two Arrays or Strings.