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 , with O(1) extra memory. The loop stops after at most m steps. The prefix table takes O(n × m) time.

Q: How is Is Subsequence related to the longest common subsequence?

s is a subsequence of t exactly when their longest common subsequence has length n , all of s . The prefix table of the first approach is the one you build for that problem. Here you only need to know whether all of s fits, so the greedy pass is enough.

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.

Follow-up

If t stays fixed and you check a million strings s against it, how would you prepare t so each check is faster than reading all of t?

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, which suggests trying many placements of s. You do not need to: matching each letter of s at the earliest place it can go is never worse than any other choice, so one left to right pass with two pointers decides it.

Dynamic programming over prefixes

Correct, but does not finish on the largest tests

Intuition

Let dp[i][j] say whether the first i letters of s fit inside the first j letters of t. They fit if they already fit without t[j-1], or if s[i-1] equals t[j-1] and the first i-1 letters fit inside t[:j-1]. The empty prefix fits everywhere, and row i reads only row i-1, so two rows of length m+1 are enough.

The table fills every cell: with s of 25,000 letters and t of 50,000, that is 1.25 × 10^9 cells.

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

Keep a pointer i to the next letter of s you need, and take the first copy of it you meet in t. That choice is safe. If a valid placement uses a later copy of s[i], swapping in the earliest copy keeps the order and leaves more of t for the rest of s. So if any placement exists, the greedy one finds it.

The loop reads each letter of t at most once and keeps two indexes: O(n + m) time and O(1) memory.

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

Searching each letter of s anywhere in t instead of after the previous match. That accepts aec in abcde.
Using one copy of a letter twice. noon is not a subsequence of moon: its single n, at index 3, cannot be both the first and the last letter.
Returning whether j reached the end of t. The loop often ends there whether or not s was found; only i tells you.
Not stopping when t runs out. abc against ab must return false.
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 questions3

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, with O(1) extra memory. The loop stops after at most m steps. The prefix table takes O(n × m) time.

How is Is Subsequence related to the longest common subsequence?

s is a subsequence of t exactly when their longest common subsequence has length n, all of s. The prefix table of the first approach is the one you build for that problem. Here you only need to know whether all of s fits, so the greedy pass is enough.

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.

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

Test #1

Test #2

Test #3

Arguments

s = "ace"
t = "abcde"

Expected Output

true