Is Subsequence

12 May 2026 0 Likes

Problem Description

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

A string is considered a subsequence if all its characters appear in another string in the same relative order, but not necessarily continuously.
Example 1:
Input: s = "abc", t = "ahbgdc"
 Output: true
Explanation: The characters a, b, and c appear in the same order inside the string "ahbgdc".
Example 2:
Input: s = "axc", t = "ahbgdc"
 Output: false
Explanation: Although a and c exist in the string, the required order for forming the subsequence is not satisfied.
Example 3:
Input: s = "", t = "ahbgdc"
 Output: true
Explanation: An empty string is always considered a valid subsequence.

Constraints

Both strings contain only English letters. The length of s and t may vary depending on platform limits.

The output should be:
true → if s is a subsequence of t
false → otherwise

An efficient solution is expected to process the strings in linear time.

Understanding the Problem

The problem is asking us to determine whether all characters of string s can be found inside string t while maintaining the same relative order.

A simple way to understand the problem is by scanning both strings from left to right. For example:

s = "abc"
t = "ahbgdc"

We start matching characters sequentially:
a → matched
b → matched
c → matched

Even though extra characters exist between them, the relative order remains correct, so "abc" is a valid subsequence. Now consider:

s = "axc"
t = "ahbgdc"

Here:
a → matched
x → not found

Since all required characters cannot be matched in order, the string is not a subsequence.

The key idea is that characters must appear in the correct sequence, even if other characters exist in between.

Hints

The first hint is to think about how two strings can be traversed simultaneously.

A useful observation is that whenever characters match, we should move forward in both strings. If characters do not match, we only move forward in the larger string t.

Using two pointers helps efficiently track progress in both strings without unnecessary repeated comparisons.

If all characters of s are matched successfully, then s is a valid subsequence.

Solutions

OPTIMAL

Two Pointer Subsequence Matching Solution

This approach uses the two-pointer technique to efficiently check whether string s is a subsequence of string t.

We maintain:
i → pointer for string s
j → pointer for string t

Both pointers start from the beginning of their respective strings.

While traversing, if the current characters match: s.charAt(i) == t.charAt(j), then we move the pointer i forward because one required character has been successfully matched.

Regardless of whether characters match or not, pointer j always moves forward because we continue scanning the larger string t.

At the end of traversal, if i == s.length(), it means every character of s was matched successfully in the correct order, so the string is a valid subsequence.

This solution is highly efficient because each string is traversed only once.
public class A_Two_Pointers {

    public boolean isSubsequence(String s, String t) {

        int i = 0;
        int j = 0;

        while (i < s.length() && j < t.length()) {

            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }

            j++;
        }

        return i == s.length();
    }
}
class Solution:

    def isSubsequence(self, s, t):

        i = 0
        j = 0

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

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

            j += 1

        return i == len(s)
Time Complexity
O(n)

Where:
n = length of string t
Space Complexity
O(1)

Conclusion

The Is Subsequence problem is a fundamental string problem that introduces the practical use of the two-pointer technique.

The problem teaches how to efficiently compare sequences while preserving relative order without requiring continuous matching.

Mastering this problem helps build a strong understanding of string traversal, pointer-based processing, and sequence matching, which are commonly used in coding interviews and real-world applications.

💬 Comments