Problem statement

Given two strings s and t, return true if s is a subsequence of t — obtainable from t by deleting some (possibly zero) characters without changing the order of the rest.

Example 1

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

Example 2

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

Constraints

• 0 <= s.length <= 10
• 0 <= t.length <= 30
• Lowercase English letters.

Hints for Is Subsequence

1. Hint 1

   Walk through t once, advancing a pointer into s on every match.

2. Hint 2

   s is a subsequence exactly when the s-pointer reaches the end.

How to solve Is Subsequence

A subsequence keeps order but allows gaps, so matching is greedy: walk t once and, whenever the current character is the one you are waiting for in s, consume it. Taking the earliest possible match is always safe, so no backtracking is ever needed.

Approach

1. Keep an index i into s, starting at zero.
2. Scan t from left to right.
3. If i is still in range and t's current character equals s[i], advance i.
4. After the scan, s is a subsequence exactly when i reached the end of s.

Why it works

Matching s[i] at the earliest opportunity is optimal by an exchange argument: if some valid embedding matches s[i] later, moving that match earlier still leaves every subsequent character of s available — the remaining suffix of t is only larger. So greedy never forfeits a match that exists, meaning failure to consume all of s proves no embedding exists at all.

Complexity

• Time — O(|t|)
• Space — O(1)

Pitfalls

• Guard i against running past the end of s before comparing, or the last matches read out of bounds.
• An empty s is a subsequence of anything — the check i == |s| handles it with no special case.
• Do not advance i on a mismatch; only t moves unconditionally.
• Never restart the scan on a mismatch — that is the O(n·m) trap this greedy avoids.

Reference solution

Python

def isSubsequence(s: str, t: str) -> bool:
    i = 0
    for ch in t:
        if i < len(s) and s[i] == ch:
            i += 1
    return i == len(s)

Java

public static boolean isSubsequence(String s, String t) {
    int i = 0;
    for (int j = 0; j < t.length(); j++) {
        if (i < s.length() && s.charAt(i) == t.charAt(j)) i++;
    }
    return i == s.length();
}

C++

bool isSubsequence(string s, string t) {
    size_t i = 0;
    for (size_t j = 0; j < t.size(); j++) {
        if (i < s.size() && s[i] == t[j]) i++;
    }
    return i == s.size();
}

JavaScript

var isSubsequence = function(s, t) {
    let i = 0;
    for (const ch of t) {
        if (i < s.length && s[i] === ch) i++;
    }
    return i === s.length;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More strings problems

• Binary Tree Paths Easy
• Find Most Frequent Vowel and Consonant Easy
• Maximum Difference Between Even and Odd Frequency I Easy
• Find Valid Pair of Adjacent Digits in String Easy
• Count the Number of Special Characters I Easy
• Find Maximum Number of String Pairs Easy