Problem Description

You are given two strings s and t. Your task is to determine if s is a subsequence of t.

A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. In other words, you can obtain a subsequence by removing characters from the original string while keeping the relative positions of the remaining characters unchanged.

For example:

• "ace" is a subsequence of "abcde" because you can delete 'b' and 'd' to get "ace"
• "aec" is not a subsequence of "abcde" because although all characters exist, they don't appear in the correct order

The function should return true if s is a subsequence of t, and false otherwise.

The solution uses a two-pointer approach where pointer i tracks the position in string s and pointer j tracks the position in string t. As we iterate through both strings:

• When characters at positions i and j match, we move both pointers forward
• When they don't match, we only move pointer j forward to continue searching in t
• If we successfully match all characters in s (when i reaches the end of s), then s is a subsequence of t

Intuition

To check if s is a subsequence of t, we need to find all characters of s in t while maintaining their original order. Think of it like reading through a book (t) and trying to find specific words (s) in sequence - you can skip words in between, but the words you're looking for must appear in the correct order.

The key insight is that we need to traverse through string t and try to match characters from string s one by one. Since we must maintain the order of characters in s, once we find a matching character, we should look for the next character of s starting from the current position in t, not from the beginning.

This naturally leads us to a greedy approach: whenever we find a character in t that matches the current character we're looking for in s, we immediately take it. We don't need to consider other occurrences of the same character later in t because:

1. Taking the first occurrence won't prevent us from finding subsequent characters of s
2. If a valid subsequence exists, using the earliest possible matches will always work

For example, checking if "abc" is a subsequence of "ahbgdc":

• We look for 'a' and find it at position 0
• We look for 'b' starting from position 1 and find it at position 2
• We look for 'c' starting from position 3 and find it at position 5
• All characters found in order → "abc" is a subsequence

This greedy scanning process can be efficiently implemented using two pointers: one to track our progress through s (what we're looking for) and another to scan through t (where we're looking).

Solution Approach

The solution implements a two-pointer technique to efficiently check if s is a subsequence of t.

Algorithm Steps:

1. Initialize two pointers: i = 0 for string s and j = 0 for string t

2. Iterate through both strings simultaneously using a while loop with condition i < len(s) and j < len(t):

   • Compare characters at current positions: s[i] and t[j]
   • If they match (s[i] == t[j]), increment i to move to the next character in s
   • Always increment j to move to the next character in t regardless of whether there's a match

3. After the loop ends, check if i == len(s):

   • If true, all characters of s were found in t in order, so s is a subsequence
   • If false, we couldn't find all characters of s in t, so s is not a subsequence

Why the algorithm works:

• Pointer i only advances when we find a matching character, ensuring we match all characters of s in sequence
• Pointer j always advances, allowing us to scan through the entire string t
• The loop terminates when either:
  • We've matched all characters of s (success case: i == len(s))
  • We've scanned all of t but haven't matched all of s (failure case: j == len(t) but i < len(s))

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of string t, as we traverse t at most once
• Space Complexity: O(1) as we only use two pointers regardless of input size

Example Walkthrough

Let's walk through checking if s = "ace" is a subsequence of t = "abcde".

Initial Setup:

• s = "ace" (length 3)
• t = "abcde" (length 5)
• i = 0 (pointer for s)
• j = 0 (pointer for t)

Step-by-step execution:

Iteration 1:

• Compare s[0] = 'a' with t[0] = 'a'
• They match! Increment i to 1
• Increment j to 1
• Continue since i < 3 and j < 5

Iteration 2:

• Compare s[1] = 'c' with t[1] = 'b'
• No match. Keep i at 1
• Increment j to 2
• Continue since i < 3 and j < 5

Iteration 3:

• Compare s[1] = 'c' with t[2] = 'c'
• They match! Increment i to 2
• Increment j to 3
• Continue since i < 3 and j < 5

Iteration 4:

• Compare s[2] = 'e' with t[3] = 'd'
• No match. Keep i at 2
• Increment j to 4
• Continue since i < 3 and j < 5

Iteration 5:

• Compare s[2] = 'e' with t[4] = 'e'
• They match! Increment i to 3
• Increment j to 5
• Loop ends since j = 5 (reached end of t)

Final Check:

• i = 3 which equals len(s) = 3
• All characters of s were found in order
• Return true - "ace" is a subsequence of "abcde"

The matched characters were at positions 0, 2, and 4 in string t, maintaining the original order from string s.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n) where n is the length of string t. In the worst case, we need to traverse the entire string t once. Even though we also traverse string s, we never go beyond the length of t since both pointers move forward together and the loop terminates when either i reaches the end of s or j reaches the end of t. The reference answer states O(m + n), but since we traverse at most n characters (length of t), and i can increment at most m times (length of s), where m ≤ n for a valid subsequence, the complexity simplifies to O(n).

Space Complexity: O(1). The algorithm uses only two pointer variables i and j regardless of the input size, requiring constant extra space.

Common Pitfalls

1. Not Handling Empty Strings Correctly

A common mistake is not considering edge cases where one or both strings are empty. While the provided solution handles these cases correctly, developers might overcomplicate the logic with unnecessary special case checks.

Pitfall Example:

def isSubsequence(self, s: str, t: str) -> bool:
    # Unnecessary edge case handling that complicates the code
    if not s and not t:
        return True
    if not t:
        return False
    if not s:
        return True
    # ... rest of the logic

Why the Original Solution Works: The two-pointer approach naturally handles empty strings:

• If s is empty, s_pointer starts at 0 and len(s) is 0, so the while loop never executes and the function returns True (empty string is a subsequence of any string)
• If t is empty but s is not, the while loop never executes and s_pointer remains 0, returning False

2. Incorrect Pointer Movement Logic

A frequent error is moving both pointers only when characters match, forgetting to advance the t_pointer when characters don't match.

Incorrect Implementation:

def isSubsequence(self, s: str, t: str) -> bool:
    s_pointer = 0
    t_pointer = 0
  
    while s_pointer < len(s) and t_pointer < len(t):
        if s[s_pointer] == t[t_pointer]:
            s_pointer += 1
            t_pointer += 1  # WRONG: Only moving t_pointer here
        # Missing: t_pointer should advance even when no match
  
    return s_pointer == len(s)

Solution: Always advance t_pointer regardless of whether there's a match:

while s_pointer < len(s) and t_pointer < len(t):
    if s[s_pointer] == t[t_pointer]:
        s_pointer += 1
    t_pointer += 1  # Always advance t_pointer

3. Using Incorrect Loop Termination Condition

Some implementations use or instead of and in the while loop condition, which causes premature termination.

Incorrect Implementation:

def isSubsequence(self, s: str, t: str) -> bool:
    s_pointer = 0
    t_pointer = 0
  
    # WRONG: Using 'or' causes loop to continue even after one string is exhausted
    while s_pointer < len(s) or t_pointer < len(t):
        if s[s_pointer] == t[t_pointer]:  # Can cause IndexError
            s_pointer += 1
        t_pointer += 1
  
    return s_pointer == len(s)

Why This Fails: Using or allows the loop to continue when one pointer has reached the end, potentially causing an IndexError when trying to access characters beyond the string length.

Solution: Use and to ensure both pointers are within bounds:

while s_pointer < len(s) and t_pointer < len(t):
    # Safe to access both s[s_pointer] and t[t_pointer]

4. Attempting to Optimize with Early Return Inside Loop

While adding an early return when all characters are matched seems like an optimization, it can make the code less clean without providing significant performance benefits.

Overly Complex Version:

def isSubsequence(self, s: str, t: str) -> bool:
    s_pointer = 0
    t_pointer = 0
  
    while s_pointer < len(s) and t_pointer < len(t):
        if s[s_pointer] == t[t_pointer]:
            s_pointer += 1
            if s_pointer == len(s):  # Unnecessary early return
                return True
        t_pointer += 1
  
    return s_pointer == len(s)

Why Original is Better: The original solution is cleaner and the performance difference is negligible since we still need to check the condition either way. The single return statement at the end makes the code more readable and maintainable.