Is Subsequence

Easy#392two arrays

You get two strings, a short one and a long one. Find out whether you can get the short one from the long one by crossing out some of its letters, without changing the order of the rest. Our examples: "cat" in "chart" — yes; "tac" in "chart" — no.

392 Is SubsequenceWalkthrough · 1×

Example: s = "cat", t = "chart". j walks along t every step, i walks along s only when the letters match.

st0c1a2ti0c1h2a3r4t
not reached yetunder a pointermatchedskipped in t

i starts at the first letter of s, "c": the letter to find first

01/22
restart · back · play · step
Speed
1function isSubsequence(s, t):
2 i = 0
3 j = 0
4 while i < len(s) and j < len(t):
5 if s[i] == t[j]:
6 i = i + 1
7 j = j + 1
8 return i == len(s)
state
i
0
j
–
s[i]
c
t[j]
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. Taking the first matching letter of t is never worse than taking a later one: whatever fits after a later match also fits after the earlier one, because more of t is left.
  2. A letter of t that is not the one we look for is of no use later either: the next letters of s have to come after the current one, and this letter is before it.
  3. If i reaches the end of s, every letter is found in order: yes. If t runs out first, a letter of s has no place after the ones before it: no.

Complexity

Time O(n), where n is the length of t: j moves one letter every step, so the loop runs at most n times. Memory O(1): only two indices.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.