Check If a String Is a Subsequence of Another String

Easy10–15 min

Topics

StringTwo Pointer

Companies

AmazonGoogleAdobeMicrosoft

Given two strings s and t, return true if s is a subsequence of t — meaning every character of s appears in t, in the same relative order, though not necessarily contiguously. Searching for each character of s across all of t from scratch works, but it repeats work every scan already did. The two-pointer technique walks both strings forward together in a single pass: advance the pointer into t on every step, and advance the pointer into s only when the current characters match. Neither pointer ever moves backward, so t is scanned exactly once no matter how the characters line up.

Test Case 1:

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

Output:true

Explanation:'a', 'b', and 'c' appear in t in that same relative order.

Test Case 2:

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

Output:false

Explanation:There's no 'x' in t after the 'a', so s can't be matched in order.

Test Case 3:

Input:s = "", t = "abc"

Output:true

Explanation:An empty string is trivially a subsequence of anything.

Constraints

◆0 ≤ s.length ≤ 100
◆0 ≤ t.length ≤ 10⁴
◆s and t consist of lowercase English letters only

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

🧪Try your own test case

s (lowercase) — 1-6 lowercase letterst (lowercase) — 1-12 lowercase letters

1	class Solution {
2	public boolean isSubsequence(String s, String t) {
3	int i = 0, j = 0;
4	while (i < s.length() && j < t.length()) {
5	if (s.charAt(i) == t.charAt(j)) i++;
6	j++;
7	}
8	return i == s.length();
9	}
10	}
11

↑j

Variables

i0

j0

INITIALIZE

Start i (into s) and j (into t) both at 0. j always advances; i advances only on a match.

Step 1 / 14

Approach & Solutions

Brute Force

Brute

For every character of s, scan t from the very beginning looking for the first still-unused occurrence of that character, skipping over indices already claimed by earlier characters. Correct, but every single character of s triggers a fresh scan across t, even though most of the earlier part of t has already been ruled out.

TimeO(n · m)

SpaceO(1)

Java

Try it out

class Solution {
    public boolean isSubsequence(String s, String t) {
        int usedUpTo = -1;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int found = -1;
            for (int j = 0; j < t.length(); j++) {
                if (j > usedUpTo && t.charAt(j) == c) { found = j; break; }
            }
            if (found == -1) return false;
            usedUpTo = found;
        }
        return true;
    }
}

Optimal — Two Pointers

Optimal

Walk two pointers forward at the same time: one over s, one over t. Advance the t pointer on every step; advance the s pointer only when the characters currently match. Neither pointer ever moves backward, so t is scanned exactly once no matter how it lines up with s. If the s pointer reaches the end, every character of s was matched in order.

TimeO(m)