NUHMAN.com

📘 Problem Statement

Given two strings s and t, return true if s is a subsequence of t, or false otherwise.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

📚 Example:

python

Input:
s = "abc", t = "ahbgdc"
Output:
true
python

Input:
s = "axc", t = "ahbgdc"
Output:
false

🧠 Key Insight

To determine whether s is a subsequence of t, we need to check if we can find all the characters of s in t while maintaining their relative order. A simple approach to solve this problem is by using the two-pointer technique.

💡 Approach

1. Two Pointers Technique:

• Use two pointers, one for string s and another for string t. Traverse both strings, trying to match each character of s with the characters of t.

1. Traverse Through Both Strings:

• Move the pointer on t to check every character.
• If the character in t matches the character in s, move the pointer for s to the next character.
• Continue this process until you either match all characters of s or finish the string t.

1. Return Result:

• If you successfully match all characters of s, return True.
• If you finish traversing t without matching all characters of s, return False.

🐍 Python Code

python

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        # Initialize pointers for both strings
        i, j = 0, 0
        
        # Traverse the string t with pointer j
        while i < len(s) and j < len(t):
            if s[i] == t[j]:  # If characters match, move pointer i
                i += 1
            j += 1  # Always move pointer j
        
        # If pointer i has traversed all of s, return True
        return i == len(s)

🔍 Step-by-Step Explanation

1. Initialize Pointers:

python

i, j = 0, 0

• Pointer i represents the current character in s.
• Pointer j represents the current character in t.

2. Traverse Both Strings:

python

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

• The loop continues as long as both pointers are within bounds.
• The goal is to match each character of s with a character in t while keeping track of their relative order.

3. Check for Matching Characters:

python

if s[i] == t[j]:
    i += 1

• If the characters at s[i] and t[j] match, increment the pointer i to move to the next character in s.
• The pointer j always moves forward regardless of whether there's a match.

4. Move Pointer j:

python

j += 1

• The pointer j always moves forward to check the next character in t.

5. Check If All Characters of s Are Matched:

python

return i == len(s)

• If i reaches the length of s, it means all characters in s have been matched in t, and we return True.
• If i doesn’t reach the end of s after the loop, return False, indicating that not all characters of s were found in t in the correct order.

💡 Example Walkthrough

Example 1:

python

Input:
s = "abc", t = "ahbgdc"
Output:
true

1. First Character (s[0] = 'a'):

• t[0] = 'a' matches s[0], so move pointer i to 1.

1. Second Character (s[1] = 'b'):

• Continue traversing t until t[2] = 'b' matches s[1], so move pointer i to 2.

1. Third Character (s[2] = 'c'):

• Continue traversing t until t[4] = 'c' matches s[2], so move pointer i to 3.

1. Exit: Since i equals the length of s, return True.

Example 2:

python

Input:
s = "axc", t = "ahbgdc"
Output:
false

1. First Character (s[0] = 'a'):

• t[0] = 'a' matches s[0], so move pointer i to 1.

1. Second Character (s[1] = 'x'):

• Continue traversing t until we find t[3] = 'g' and t[4] = 'd', but there is no match for s[1] = 'x'.

1. Exit: Since i did not reach the length of s, return False.

⏱️ Time & Space Complexity

MetricComplexityTime ComplexityO(n)Space ComplexityO(1)

• Time Complexity:
• We traverse each string at most once, so the time complexity is O(n), where n is the length of the longer string (t).
• Space Complexity:
• The algorithm uses a constant amount of extra space for the two pointers, so the space complexity is O(1).

🧵 Final Thoughts

LeetCode 392 is an excellent problem for practicing the two-pointer technique to check if one string is a subsequence of another. This approach is both time-efficient and space-efficient, making it an optimal solution for such problems. The problem emphasizes the importance of maintaining relative order while checking subsequences, and the two-pointer technique is a natural fit for this challenge.