easy

Is Subsequence

Check whether one string is a subsequence of another.

1. Define the problem

Is Subsequence

Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence is formed by deleting some (or no) characters from t without disturbing the relative positions of the remaining characters. Use two pointers moving in the same direction through s and t: advance the s-pointer only on a match, and always advance the t-pointer.

Constraints

  • 0 ≤ s.length ≤ 100
  • 0 ≤ t.length ≤ 104
  • s and t consist only of lowercase English letters

Example

Inputs = "abc", t = "ahbgdc"
Outputtrue

Explanation Every character of s appears in t in order: a, then b, then c.

2. Know the words first

In plain terms

Subsequence
A set of characters taken from a string in the same order they originally appear, even if other characters sit between them — for example, 'ace' is a subsequence of 'abcde'.
3. Visualize the solution

Advance the t-pointer, advance the s-pointer only on a match

Advance the t-pointer, advance the s-pointer only on a match
Statusinit

i=0 (looking for 'a') and j=0 ('a') — match. i advances to 1.

What happens in this step

i = 0 (need 'a'), j = 0 (value 'a')
t[j] == s[i]

Match — i advances to 1, now looking for s[1]='b'.
Step 1 of 4

Steps to visualize

  1. Place a pointer i at the start of s and a pointer j at the start of t.
  2. Advance j through t one character at a time.
  3. Whenever tj matches si, advance i as well.
  4. Continue until i reaches the end of s (a match) or j reaches the end of t (no match).
  5. s is a subsequence of t exactly when i reaches the end of s.
4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Advance the t-pointer, advance the s-pointer only on a match
Statusinit

i=0 (looking for 'a') and j=0 ('a') — match. i advances to 1.

What happens in this step

i = 0 (need 'a'), j = 0 (value 'a')
t[j] == s[i]

Match — i advances to 1, now looking for s[1]='b'.
Step 1 of 4
5. Solution

Solution

solution.tsTypeScript
function isSubsequence(s, t) {
  if (s.length === 0) {
    return true;
  }

  let i = 0;

  for (let j = 0; j < t.length; j++) {
    if (s[i] === t[j]) {
      i++;
      if (i === s.length) {
        return true;
      }
    }
  }

  return i === s.length;
}
Time
O(n)
Space
O(1)
6. Test cases

Test cases

InputExpectedCovers
s = "abc", t = "ahbgdc"trueexample from the docstring
s = "", t = "ahbgdc"trueempty s is trivially a subsequence of anything
s = "abcde", t = "ab"falses is longer than t, so it cannot fit
s = "abc", t = "abc"trues and t are identical
s = "axc", t = "ahbgdc"falsea middle character of s never appears in the remaining part of t
s = "a", t = ""falseempty t cannot contain a non-empty s
s = "a", t = "a"truesmallest non-trivial matching case, single characters

Keep reading

TopicDescription
Two PointersScan a sorted array or string from both ends at once to find pairs, remove duplicates, or reverse data in O(n).
Valid PalindromeCheck whether a string reads the same forwards and backwards, ignoring case and punctuation.
Merge Sorted ArrayMerge two sorted arrays into one sorted array in place.
Remove Duplicates from Sorted ArrayRemove duplicate values from a sorted array in place and return the new length.
Move ZeroesMove every zero in an array to the end while keeping the other numbers in order.
Two Sum II - Input Array Is SortedFind two numbers in a sorted array that add up to a target value.