Mastering the Is Subsequence Problem in Python – LeetCode 75 Explained

The Is Subsequence problem from LeetCode 75 is a popular interview question that checks your understanding of character matching, greedy algorithms, and two-pointer traversal. The task is simple: determine if one string is a subsequence of another. But to do it efficiently, especially when dealing with long strings, is where the value lies.

In this blog post, we’ll explore the Is Subsequence problem using a clean, optimal Python solution. We’ll break down the logic, walk through examples, and discuss its relevance in interviews and real-world string processing tasks.

Problem Statement

Given two strings s and t, check if s is subsequence of t.

What does “subsequence” mean?

A string s is a subsequence of string t if all the characters of s appear in t in the same order, but not necessarily contiguously. This means you can delete some (or even zero) characters from t without rearranging the remaining characters, and still be able to form s.

In simpler terms:

If you can match every character in s while reading through t from left to right, then s is a subsequence of t.

You do not need to modify the characters in t.

You are only allowed to skip characters, keeping the rest in the same sequence.

Examples

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

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

Python Solution – Step-by-Step Explanation

Let’s look at a clean and optimal Python implementation using the two-pointer technique:

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        i, j = 0, 0

        while i < len(s) and j < len(t):
            if s[i] == t[j]:
                i += 1
            j += 1

        return i == len(s)

Step 1: Initialize Two Pointers

i, j = 0, 0

• i points to the current character in string s
• j points to the current character in string t

Step 2: Traverse Both Strings

while i < len(s) and j < len(t):
    if s[i] == t[j]:
        i += 1
    j += 1

• Compare characters from both strings.
• If a match is found, move the pointer i in s.
• Regardless of match, move the pointer j in t.
• This ensures that we preserve the order of characters.

Step 3: Check the Result

return i == len(s)

• If i has reached the end of s, it means all characters of s were found in t in order — so s is a subsequence.

Why This Solution Works

• It respects the order of characters.
• It doesn’t require extra space.
• It handles edge cases like empty strings gracefully.
• It uses a simple and effective greedy approach with linear time complexity.

Time and Space Complexity

Metric	Value
Time Complexity	O(n)
Space Complexity	O(1)

Where n is the length of string t.

Edge Cases to Consider

Case	Output	Explanation
s = ""	True	An empty string is a subsequence of any string.
s = "abc", t = "abc"	True	Exact match.
s = "abc", t = "aabbcc"	True	Characters are in order even with duplicates.
s = "abc", t = "acb"	False	Order is not maintained.

Real-World Applications

• Autocomplete systems: Matching user input with valid suggestions.
• File path filtering: Checking if a path matches a pattern.
• Search engines: Simplifying queries to find subsequence matches.
• Interview prep: Common in big tech coding assessments.

Conclusion

The Is Subsequence problem is a foundational coding challenge that teaches you how to use pointer-based string traversal effectively. It emphasizes the importance of character order and efficient comparison, both of which are common in software engineering tasks.

Mastering this problem not only strengthens your problem-solving skills but also gives you confidence in tackling more complex string manipulation and pattern matching challenges.

Related Read

Mastering the Move Zeroes Problem in Python – LeetCode 75 Explained

Stay tuned on Vanita.ai for more LeetCode 75 breakdowns, algorithm walkthroughs, and real-world coding insights.