Is Subsequence

Q: What is the time complexity of Is Subsequence?

The two pointer solution runs in O(n + m) time, where n and m are the lengths of s and t , and it uses O(1) extra memory. In practice the loop stops after at most m steps. The prefix table takes O(n × m) time.

Q: Why does the greedy two pointer approach work for Is Subsequence?

Matching a letter of s at its earliest possible place in t leaves the longest possible rest of t for the remaining letters. Any placement that uses a later copy can be changed to use the earlier one without breaking the order, so if any placement exists, the greedy one finds it.

Q: How do you check many strings against the same t quickly?

Prepare t once: for each letter, store the sorted list of indexes where it appears. To place s[i] , binary search that letter's list for the first index after the previous match. Each check then costs O(n log m) instead of O(m) .

EasyTwo pointers

+10

You get two strings, s and t. Return true if you can turn t into s by deleting some of its letters (possibly none) while the remaining letters keep their order, and false otherwise. For example, ace is a subsequence of abcde, but aec is not.

Function

isSubsequence(s: string, t: string) → boolean

sstring: the string to look for
tstring: the string to delete letters from
Returnsboolean: true if s can be read inside t in order, possibly with gaps

Constraints

1 ≤ s.length ≤ 3 × 10⁴
1 ≤ t.length ≤ 5 × 10⁴
s and t contain only lowercase English letters.

Examples

Input: s = "ace"t = "abcde"
Output: true
Explanation: Delete b and d from abcde and ace is left, in the same order.

Input: s = "aec"t = "abcde"
Output: false
Explanation: t has all three letters, but the only c sits before the only e. After you use the e at index 4, no c is left to its right.

Input: s = "moon"t = "monsoon"
Output: true
Explanation: Use the m at index 0, the os at indexes 1 and 4, and the n at index 6 of monsoon. The letters in between are deleted.

+20 hidden tests on Submit

Follow-up

Suppose t stays the same and you have to check a million different strings s against it. How would you prepare t so each check is faster than reading all of t again?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A subsequence may skip letters of t anywhere, so it can look as if you have to try many ways of placing s inside t. You do not. Matching each letter of s at the earliest place it can go is never worse than any other choice, and that turns the search into one left to right pass with two pointers.

Dynamic programming over prefixes

Correct, but does not finish on the largest tests

Intuition

Ask a smaller question: do the first i letters of s fit inside the first j letters of t? Call the answer dp[i][j]. If they fit inside t[:j-1], they fit inside t[:j] too, since you can delete t[j-1]. If s[i-1] equals t[j-1], you can also use that letter, and then the first i-1 letters of s must fit inside t[:j-1]. So dp[i][j] = dp[i][j-1] or (s[i-1] == t[j-1] and dp[i-1][j-1]), and the empty prefix of s fits everywhere.

Row i only reads row i-1, so two rows of length m+1 are enough. The answer is the last cell of the last row.

This is the same table you build for the longest common subsequence, and it is correct, but it fills every cell. With s of 25,000 letters and t of 50,000, that is 1.25 × 10^9 cells, far more than a single pass over the two strings needs.

Algorithm

Create a row prev of m+1 values, all true: an empty s fits in every prefix of t.
For each i from 1 to n, create a row cur with cur[0] = false.
For each j from 1 to m, set cur[j] to cur[j-1], or to prev[j-1] when s[i-1] equals t[j-1].
Replace prev with cur.
Return prev[m].

def isSubsequence(s, t):
    n, m = len(s), len(t)
    # prev[j]: the first i-1 letters of s fit inside t[:j]. An empty s fits anywhere.
    prev = [True] * (m + 1)
    for i in range(1, n + 1):
        cur = [False] * (m + 1)
        for j in range(1, m + 1):
            cur[j] = cur[j - 1] or (s[i - 1] == t[j - 1] and prev[j - 1])
        prev = cur
    return prev[m]

Two pointers with greedy matching

Intuition

Read t from left to right and keep a pointer i to the next letter of s you still need. When t[j] equals s[i], use it and move i forward. Either way, move j forward. If i reaches the end of s, every letter found a place in order.

Why is it safe to take the first match? Suppose some valid placement uses a later copy of s[i]. Swapping it for the earliest copy keeps the order and leaves more of t to the right for the rest of s, so the greedy choice never loses a placement that exists. For moon in monsoon, the pointer takes the o at index 1, skips n and s, takes the o at index 4, and ends on the n at index 6.

j visits each letter of t once and i only moves forward, so the loop runs at most m times. Two indexes are all the memory it needs.

Algorithm

Set i = 0 for s and j = 0 for t.
While both indexes are inside their strings, compare s[i] with t[j].
If they are equal, increase i.
Increase j in every case.
Return whether i equals the length of s.

def isSubsequence(s, t):
    i = j = 0
    while i < len(s) and j < len(t):
        if s[i] == t[j]:
            i += 1
        j += 1
    return i == len(s)

Pitfalls and edge cases

The two pointer loop is short, and its bugs sit at the edges.

Searching each letter of s anywhere in t instead of after the previous match. That accepts aec in abcde, where order is broken.
Using one copy of a letter twice. noon is not a subsequence of moon: moon has a single n, at index 3, and it cannot be both the first and the last letter of noon.
Returning whether j reached the end of t. The loop often ends there whether or not s was found; only i tells you.
Forgetting that s can be longer than t. abc against ab must return false, which the loop gives as long as it stops when t runs out.
Reading s[i] after i reached the end of s. In Python or Java that read throws, so check i before you compare.

Frequently asked questions4

What is the time complexity of Is Subsequence?

The two pointer solution runs in O(n + m) time, where n and m are the lengths of s and t, and it uses O(1) extra memory. In practice the loop stops after at most m steps. The prefix table takes O(n × m) time.

Why does the greedy two pointer approach work for Is Subsequence?

Matching a letter of s at its earliest possible place in t leaves the longest possible rest of t for the remaining letters. Any placement that uses a later copy can be changed to use the earlier one without breaking the order, so if any placement exists, the greedy one finds it.

How do you check many strings against the same t quickly?

Prepare t once: for each letter, store the sorted list of indexes where it appears. To place s[i], binary search that letter's list for the first index after the previous match. Each check then costs O(n log m) instead of O(m).

What is the difference between a subsequence and a substring?

A substring is a block of consecutive letters, while a subsequence may skip letters as long as the order stays the same. ace is a subsequence of abcde but not a substring of it. Every substring is a subsequence, but not the other way around.

Python

def isSubsequence(s, t):
    # Write code here

Test cases

Case 1

Case 2

Case 3

Input

s = "ace"
t = "abcde"

Expected

true