Code Logo

Is Subsequence

Published at24 Jul 2026
Created by
Easy 0 views
Like0

Given two strings s and t, return true if s is a subsequence of t, or false otherwise. A subsequence is a sequence that can be derived from another string by deleting some or no characters without changing the order of the remaining characters. For example, "ace" is a subsequence of "abcde".

A greedy two-pointer approach works efficiently: iterate through t with pointer j, and for each character in s with pointer i, move j forward until a match is found. If all characters of s are matched, return true. Otherwise, return false. This runs in O(|t|) time with O(1) space.

While simple two pointers suffices, this problem can also be solved with DP: a 2D table dp[i][j] indicates whether s[0..i-1] is a subsequence of t[0..j-1]. The recurrence is dp[i][j] = dp[i][j-1] OR (dp[i-1][j-1] AND s[i-1]==t[j-1]). The two-pointer approach is preferred for a single query.

Edge cases include empty s (always true, since empty string is a subsequence of any string), empty t with non-empty s (false), and exact matches (s equals t).

The two-pointer approach for subsequence checking works in O(n) time because each character in t is examined at most once. This greedy matching strategy works because matching earlier is always at least as good as matching later for future characters.

Example Input & Output

Example 1
Input
"abc", "ahbgdc"
Output
true
Explanation

abc is a subsequence of ahbgdc.

Example 2
Input
"a", "a"
Output
true
Explanation

Single character match.

Example 3
Input
"", "abc"
Output
true
Explanation

Empty string is always a subsequence.

Example 4
Input
"axc", "ahbgdc"
Output
false
Explanation

axc is not a subsequence.

Example 5
Input
"abc", ""
Output
false
Explanation

Non-empty s cannot be subsequence of empty t.

Algorithm Flow

Recommendation Algorithm Flow for Is Subsequence

Solution Approach

Check if string s is a subsequence of string t. Use two pointers: i for s and j for t. While both indices are within bounds, compare s[i] with t[j]. If they match, advance i. Always advance j. If i reaches the end of s, all characters have been found in order — return true. If j reaches the end of t first, return false.

function isSubsequence(s, t) {
  var i = 0, j = 0;
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) i++;
    j++;
  }
  return i === s.length;
}

The greedy matching works because we want the earliest possible match for each character in s. Once a character is matched, we move to the next character in s while continuing to scan t. The relative order is preserved because j never decrements.

Time complexity is O(len(t)), space complexity is O(1).

Best Answers

java
class Solution {
    public boolean solution(String s, String t) {
        int i = 0, j = 0;
        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) i++;
            j++;
        }
        return i == s.length();
    }
}