🔍 Check If a String is a Subsequence! | Two-Pointer Approach Explained in Python #Python #LeetCode

💡 Problem Statement:

We are given two strings s and t, and our goal is to check whether s is a subsequence of t.

🔹 What is a subsequence?

A subsequence is a string that can be obtained from another string by deleting some (or no) characters without changing the order of the remaining characters.

✅ Examples of Subsequences:

"abc" is a subsequence of "ahbgdc" → because we can remove "h", "g", and "d" from "ahbgdc" to get "abc".
"ace" is a subsequence of "abcde" → just remove "b" and "d".

❌ Examples of Non-Subsequences:

"axc" is not a subsequence of "ahbgdc" → because "x" appears in "s", but it is missing in "t".
"hello" is not a subsequence of "hlllo" → because the missing "e" prevents it from forming "hello".

🛠 Approach to Solve This Problem

We will use the Two-Pointer Technique, which is an optimal way to traverse both strings in a single pass.

🚀 Step-by-Step Explanation of the Algorithm

Step 1️⃣ - Initialize Two Pointers

We need two pointers:

i → Points to the characters in s (the smaller string).
j → Points to the characters in t (the larger string).

We start both pointers at index 0:

i, j = 0, 0

At this point:

📌 i = 0 → pointing to s[0] (first character of s)
📌 j = 0 → pointing to t[0] (first character of t)

Step 2️⃣ - Traverse the Larger String t

We now iterate through t (the larger string) using pointer j, while checking if we find the characters of s in order.

We use a while loop:

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

This ensures that we stop if either s or t has been fully checked.

Inside the loop:

If s[i] == t[j] → This means the current character in t matches the character in s, so we move i to the next character in s.

Always move j forward → Whether there’s a match or not, we always increment j to continue scanning t.

Implementation:

if s[i] == t[j]: # If characters match, move pointer in s
i += 1
j += 1 # Always move pointer in t

Step 3️⃣ - Final Check

At the end of the loop, we check:

return i == len(s)
If i has reached the length of s, that means we found all characters of s inside t in order.
If i is less than len(s), then some characters from s are missing in t, so we return False.

💻 Full Python Code Implementation

class Solution:
def isSubsequence(self, s, t): # Removed type hints for compatibility
i, j = 0, 0 # Two pointers

while i v len(s) and j v len(t):
if s[i] == t[j]: # If characters match, move pointer in s
i += 1
j += 1 # Always move pointer in t

return i == len(s) # If i reached the end of s, it's a subsequence

# Example usage:
sol = Solution()

🔢 Dry Run of the Code (Step-by-Step Execution)

Let's take an example:

s = "abc"
t = "ahbgdc"

Step s[i] t[j] Action i (Pointer for s) j (Pointer for t)
1 "a" "a" Match ✅ Move i 1 → (Next char in s) 1
2 "b" "h" No Match ❌ 1 2
3 "b" "b" Match ✅ Move i 2 → (Next char in s) 3
4 "c" "g" No Match ❌ 2 4
5 "c" "d" No Match ❌ 2 5
6 "c" "c" Match ✅ Move i 3 (End of s) 6
Since i has reached the length of s (i == 3), we return True because "abc" is a subsequence of "ahbgdc". ✅

⏳ Time Complexity Analysis
O(n) Linear Time Complexity

We traverse t only once, and s at most once, making this solution O(n) time complexity, where n is the length of t.
O(1) Constant Space Complexity

We are only using two pointers (i and j), meaning the space used is constant (O(1)).

📌 Why is This Solution Efficient?

🔹 Single Pass through t: We don’t have to compare every character of s with t, just follow the sequence.
🔹 Two-Pointer Approach: This allows us to scan t without backtracking, making it very efficient.
🔹 No Extra Space Used: We don’t store additional arrays, making it memory-efficient.

🔎 Key Takeaways from This Solution

✅ The two-pointer technique is ideal when comparing two sequences.
✅ We never modify the input strings, making it a safe and efficient approach.
✅ This approach works even if s is an empty string (returns True, since an empty string is always a subsequence).
✅ Time Complexity: O(n), Space Complexity: O(1) → Perfect for large inputs!

🔥 Example Test Cases

📢 Final Thoughts

This method is one of the best ways to solve the subsequence problem efficiently. If you’re preparing for coding interviews, mastering the two-pointer technique will help you tackle many similar problems!

💙 If this helped you, don’t forget to like, share, and subscribe for more Python coding tutorials! 💙

#Python #LeetCode #TwoPointers #Algorithms #DataStructures #PythonShorts #CodingInterview #LearnPython #Programming