392. Is Subsequence - Detailed Explanation

Problem statement

Description:
Given two strings, s and t, determine whether s is a subsequence of t. A subsequence of a string is formed by deleting some, or none, of the characters from the original string without changing the relative order of the remaining characters.

Definition:

• Subsequence: A string s is a subsequence of t if you can remove zero or more characters from t to get s while preserving the order of the characters.

This question is the plainest instance of the Two Pointers pattern, the technique that moves two indices through the input at different speeds instead of nesting one loop inside another. Here one index advances only on a match, the other advances every step. That pairing shows up repeatedly, as the summary of the most common LeetCode patterns shows.

Examples:

• Example 1:

  • Input: s = "abc", t = "ahbgdc"
  • Output: true
  • Explanation:
    The characters "a", "b", "c" appear in "ahbgdc" in the same order, that is "a", then "b", then "c".

• Example 2:

  • Input: s = "axc", t = "ahbgdc"
  • Output: false
  • Explanation:
    Although "a" and "c" appear in "ahbgdc", the letter "x" does not appear in the correct order to form "axc".

Constraints:

• 0 ≤ s.length ≤ 100
• 0 ≤ t.length ≤ 10⁴
• Both s and t consist of lowercase English letters.

Hints

• Hint 1:
  Use two pointers, one for s and one for t. Traverse t and check whether the current character matches the current character in s. If it does, move the pointer in s.

• Hint 2:
  Once you reach the end of s, you know that all characters of s have been found in order in t.

• Hint 3:
  If you finish traversing t without advancing the pointer in s to the end, then s is not a subsequence of t.

Approaches

Two pointer approach (optimal)

Idea:

• Use one pointer (i) to iterate over s and another pointer (j) to iterate over t.
• For each character in t, check whether it matches the current character in s, meaning s[i].
• If they match, move the pointer in s forward.
• Continue until either pointer reaches the end of its own string.
• If the pointer for s reaches the end, meaning i == s.length, then s is a subsequence of t.

Steps:

1. Initialize two pointers: i = 0 for s and j = 0 for t.
2. While both i < s.length and j < t.length:
   • If s[i] == t[j], increment i, since you found a matching character.
   • Always increment j to move to the next character in t.
3. After the loop, check whether i equals s.length. If it does, return true. Otherwise, return false.

Dynamic programming or binary search (for multiple queries)

Idea:

• Preprocess t to record the indices of each character.
• For each query string s, use binary search to find whether each character in s appears in t after the index of the previous character.
• This method helps when you run many queries against the same string t.

Note:
For a single query, the two pointer approach is simpler and just as fast.

Detailed walkthrough (two pointer approach)

Consider the example where s = "abc" and t = "ahbgdc".

1. Initialization:

   • i = 0 (points to 'a' in s)
   • j = 0 (points to 'a' in t)

2. Iteration:

   • Step 1: Compare s[0] ('a') with t[0] ('a'):
     • They match → increment i to 1.
     • Increment j to 1.
   • Step 2: Now compare s[1] ('b') with t[1] ('h'):
     • No match → keep i at 1, increment j to 2.
   • Step 3: Compare s[1] ('b') with t[2] ('b'):
     • They match → increment i to 2, increment j to 3.
   • Step 4: Compare s[2] ('c') with t[3] ('g'):
     • No match → keep i at 2, increment j to 4.
   • Step 5: Compare s[2] ('c') with t[4] ('d'):
     • No match → keep i at 2, increment j to 5.
   • Step 6: Compare s[2] ('c') with t[5] ('c'):
     • They match → increment i to 3, increment j to 6.

3. Conclusion:

   • Now i == s.length (3 == 3), so all characters of s were found in t in order.
   • Return true.

Code implementation

Python code