Is Subsequence | AlgoDrill Interview Course

Given strings candidate and text, return whether every character of candidate appears in text in the same relative order. The matching characters do not need to be adjacent.

Suppose we are checking whether "ace" is a subsequence of "abcde". After matching a at the beginning of the text, no earlier text position can help match c or e. A subsequence must preserve order, so the search for the next required character should continue from the next text position rather than begin again.

Use one pointer for the next character still required from candidate and another for the text position currently being inspected. The text pointer moves after every comparison because that text position has been considered. The candidate pointer moves only after a match because a mismatch does not satisfy the current requirement.

Before each comparison, every candidate character before candidate_index has already been matched in order somewhere before text_index. The character at candidate_index is the next one still needed. If the candidate pointer reaches the end, every required character has been found. If the text ends first, at least one required character remains unmatched.

An empty candidate is a subsequence of every string because it has no required characters. The code handles this automatically because i == len(s) before the loop begins.

How does the scan match "ace" inside "abcde"?

1 / 6

candidate

text

Both pointers begin at a. The characters match, so the first requirement is satisfied.

While checking "ace" against "abcde", the required character is c and the current text character is b. Why must only the text pointer move?

In the implementation, i points to the next required character in s, and j points to the character currently being inspected in t.

1class Solution:

2 def isSubsequence(self, s: str, t: str) -> bool:

3 i = j = 0

4 while i < len(s) and j < len(t):

5 if s[i] == t[j]:

6 i += 1

7 j += 1

8

9 return i == len(s)

Time: O(n)Space: O(1)

Time is O(n), where n is the length of text. Each text character is inspected at most once, and the scan may stop earlier after every candidate character has been matched. The two indices use O(1) auxiliary space.