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 no) 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.

Examples:

• Example 1:

  • Input: s = "abc", t = "ahbgdc"
  • Output: true
  • Explanation:
    The characters "a", "b", "c" appear in "ahbgdc" in the same order (i.e. "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 if 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 and haven’t advanced 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 if it matches the current character in s (i.e. s[i]).
• If they match, move the pointer in s forward.
• Continue until either pointer reaches the end of its respective string.
• If the pointer for s reaches the end (i.e. 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 (found a matching character).
   • Always increment j to move to the next character in t.
3. After the loop, check if i is equal to s.length. If yes, return true; otherwise, return false.

3.2. Dynamic Programming / 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 previous character’s index.
• This method is useful if you have multiple queries against the same string t.

Note:
For a single query, the two-pointer approach is more straightforward and efficient.

Detailed Walkthrough (Two-Pointer Approach)

Let’s 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