Is Subsequence

Easy Arrays & Hashing Two Pointer Original on LeetCode

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 <= 100
  • 0 <= t.length <= 10^4
  • s and t consist 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.

00:00
Testcase

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.

ApproachTimeSpace
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)

TimeO(m · n)Every cell of the table is filled once.
SpaceO(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.

  1. Create a table dp of size (m + 1) x (n + 1) where m = |s|, n = |t|.
  2. 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]).
  3. 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;
    }
}

2Optimal (two pointers, greedy match)

TimeO(n)t is scanned once.
SpaceO(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.

  1. Set i = 0.
  2. For each character c of t: if i < |s| and c == s[i], increment i.
  3. 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();
    }
}

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".