392. Is Subsequence - Solution & Explanation

The problem

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

A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).

Example 1:

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

Example 2:

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

Constraints:

0 <= s.length <= 100
0 <= t.length <= 10⁴
s and t consist only of lowercase English letters.

Follow up: Suppose there are lots of incoming s, say s₁, s₂, ..., s_k where k >= 10⁹, and you want to check one by one to see if t has its subsequence. In this scenario, how would you change your code?

Approach overview

Problem Overview: Given two strings s and t, determine whether s is a subsequence of t. A subsequence keeps the relative order of characters but does not require them to be contiguous. The task is to scan t and verify that every character in s appears in order.

Approach 1: Two-Pointer Technique (O(n) time, O(1) space)

This is the standard solution using the two pointers pattern. Maintain one pointer for s and another for t. Iterate through t; whenever t[j] matches s[i], advance the pointer for s. Continue scanning until either all characters in s are matched or t is exhausted. The key insight: subsequence checking only requires preserving order, so a single pass through t is enough. This approach runs in O(|t|) time and O(1) space because it only uses two indices. It works well when you check a single pair of strings and is the most common interview solution for problems involving string traversal.

Approach 2: Preprocessing with Character Index Lists (O(n + m log n) time, O(n) space)

The follow-up version asks what happens if you must check billions of candidate strings s against the same t. Instead of scanning t every time, preprocess it by storing the indices of each character in a map. For example, build a dictionary where each character points to a sorted list of positions where it appears in t. For each character in s, use binary search to find the smallest index greater than the previously matched position. This converts repeated scanning into fast lookups. Preprocessing takes O(|t|) time and space. Each query string s then runs in O(|s| log |t|) due to binary search. This pattern appears in advanced dynamic programming and query optimization problems where the same dataset is reused.

Recommended for interviews: The two-pointer solution is what interviewers expect first. It shows you understand subsequence properties and can implement an efficient single-pass scan with O(n) time and constant space. Mentioning the preprocessing approach during follow-ups demonstrates deeper problem-solving skills and awareness of scaling when many queries share the same base string.

Approach 1: Two-Pointer Technique

The Two-Pointer Technique involves maintaining two indices, one for each string (s and t). Start both pointers at the beginning of their respective strings. Move the pointer for 's' only when there's a match with the current character at 't'. This ensures that all characters in 's' appear in 't' with the correct order. If the pointer for 's' reaches the end of 's', then 's' is a subsequence of 't'.

Python

def is_subsequence(s: str, t: str) -> bool:
    index_s, index_t = 0, 0
    while index_s < len(s) and index_t < len(t):
        if s[index_s] == t[index_t]:
            index_s += 1
        index_t += 1
    return index_s == len(s)

Java

public boolean isSubsequence(String s, String t) {
    int indexS = 0, indexT = 0;
    while (indexS < s.length() && indexT < t.length()) {
        if (s.charAt(indexS) == t.charAt(indexT)) {
            indexS++;
        }
        indexT++;
    }
    return indexS == s.length();
}

C++

#include <string>
bool isSubsequence(const std::string &s, const std::string &t) {
    int indexS = 0, indexT = 0;
    while (indexS < s.size() && indexT < t.size()) {
        if (s[indexS] == t[indexT]) {
            indexS++;
        }
        indexT++;
    }
    return indexS == s.size();
}

JavaScript

function isSubsequence(s, t) {
    let indexS = 0, indexT = 0;
    while (indexS < s.length && indexT < t.length) {
        if (s[indexS] === t[indexT]) {
            indexS++;
        }
        indexT++;
    }
    return indexS === s.length;
}

#include <stdbool.h>
#include <string.h>

bool isSubsequence(char *s, char *t) {
    int indexS = 0, indexT = 0;
    int lengthS = strlen(s), lengthT = strlen(t);
    while (indexS < lengthS && indexT < lengthT) {
        if (s[indexS] == t[indexT]) {
            indexS++;
        }
        indexT++;
    }
    return indexS == lengthS;
}

public bool IsSubsequence(string s, string t) {
    int indexS = 0, indexT = 0;
    while (indexS < s.Length && indexT < t.Length) {
        if (s[indexS] == t[indexT]) {
            indexS++;
        }
        indexT++;
    }
    return indexS == s.Length;
}

The Python solution follows the same two-pointer concept. In Python, the loop checks character matches and moves forward similarly, ensuring 's' is checked against 't' properly.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Follow-up: Using Preprocessing

For frequent 's' queries, preprocess 't' to build a map of character positions using a dictionary or hashmap structure. This allows for efficient binary search to determine if 's' is a subsequence, as only relevant sections of 't' need to be checked.

Python

from collections import defaultdict
from bisect import bisect_right

def preprocess(t):
    position_map = defaultdict(list)
    for index, char in enumerate(t):
        position_map[char].append(index)
    return position_map

def is_subsequence(s, t):
    position_map = preprocess(t)
    previous_position = -1
    for char in s:
        if char not in position_map:
            return False
        position_list = position_map[char]
        next_position_index = bisect_right(position_list, previous_position)
        if next_position_index == len(position_list):
            return False
        previous_position = position_list[next_position_index]
    return True

This Python solution uses a map to store positions of each character in 't'. For each character in 's', it performs a binary search using the 'bisect' module to locate the next valid position in 't'. This avoids full scans and enhances efficiency for large numbers of 's'.

Complexity

Preprocessing Time Complexity: O(n) for preparing the map where n is the length of 't'.
Checking Time Complexity: O(mlog(k)) for each 's', where m is the length of 's' and k is the average number of occurrences of each character in 't'.
Space Complexity: O(n) for the map storage.

Try this approach in the editor

Approach 3: Two Pointers

We define two pointers i and j to point to the initial position of the string s and t respectively. Each time we compare the two characters pointed to by the two pointers, if they are the same, both pointers move right at the same time; if they are not the same, only j moves right. When the pointer i moves to the end of the string s, it means that s is the subsequence of t.

The time complexity is O(m + n), where m and n are the lengths of the strings s and t respectively. The space complexity is O(1).

TypeScript

function isSubsequence(s: string, t: string): boolean {
    const m = s.length;
    const n = t.length;
    let i = 0;
    for (let j = 0; i < m && j < n; ++j) {
        if (s[i] === t[j]) {
            ++i;
        }
    }
    return i === m;
}

func isSubsequence(s string, t string) bool {
	i, j, m, n := 0, 0, len(s), len(t)
	for i < m && j < n {
		if s[i] == t[j] {
			i++
		}
		j++
	}
	return i == m
}

Rust

impl Solution {
    pub fn is_subsequence(s: String, t: String) -> bool {
        let (s, t) = (s.as_bytes(), t.as_bytes());
        let n = t.len();
        let mut i = 0;
        for &c in s.iter() {
            while i < n && t[i] != c {
                i += 1;
            }
            if i == n {
                return false;
            }
            i += 1;
        }
        true
    }
}

Try this approach in the editor

Complexity comparison

Approach	Complexity
Two-Pointer Technique	Time Complexity: O(n). Space Complexity: O(1).
Follow-up: Using Preprocessing	Preprocessing Time Complexity: O(n) for preparing the map where n is the length of 't'. Checking Time Complexity: O(mlog(k)) for each 's', where m is the length of 's' and k is the average number of occurrences of each character in 't'. Space Complexity: O(n) for the map storage.
Two Pointers	–

Complexity analysis

Approach	Time	Space	When to Use
Two-Pointer Technique	O(\|t\|)	O(1)	Best for single queries where you only need to check one pair of strings.
Preprocessing with Index Lists + Binary Search	O(\|t\|) preprocessing + O(\|s\| log \|t\|) per query	O(\|t\|)	Useful when many different strings must be checked against the same base string t.

Frequently asked questions

Is Is Subsequence easy or hard?

Is Subsequence is categorized as an Easy problem on LeetCode. It focuses on understanding subsequences and applying the two-pointer technique efficiently. The follow-up involving preprocessing and binary search adds a medium-level optimization twist.

How to solve Is Subsequence in O(n)?

Use two pointers to traverse both strings. Move the pointer in t forward each step, and whenever characters match, advance the pointer in s. If the pointer for s reaches the end, s is a subsequence. This approach processes t in a single pass with O(n) time and constant space.

What is the best approach for Is Subsequence?

The two-pointer technique is the best approach for most cases. Scan string t once while advancing a pointer in s whenever characters match. This runs in O(|t|) time with O(1) extra space and is the solution typically expected in coding interviews.

What data structure is used in Is Subsequence?

The basic solution uses only two integer pointers while iterating through the strings. In the follow-up optimization, a hash map or dictionary stores lists of character indices in t, and binary search is used to quickly locate the next valid position.

What is the time complexity of Is Subsequence?

The optimal two-pointer solution runs in O(|t|) time because it scans the longer string once while matching characters from s. Space complexity is O(1) since only two indices are used. If preprocessing with binary search is used for multiple queries, each check runs in O(|s| log |t|).

Is Subsequence Python or Java solution available?

The problem can be implemented easily in Python, Java, C++, C#, JavaScript, and C using the same two-pointer logic. Each version iterates through t and advances the index in s when characters match, keeping the implementation concise.

Is Is Subsequence asked at Google, Amazon, or Meta?

Is Subsequence appears frequently in coding interviews at large tech companies because it tests fundamental string traversal and pointer logic. Variations of the problem show up in interview prep sets used by companies like Google, Amazon, and Meta.

Is Subsequence solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique

Approach 2: Follow-up: Using Preprocessing

Approach 3: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Is Subsequence solution and explanation

The problem

Approach overview

Approach 1: Two-Pointer Technique

Approach 2: Follow-up: Using Preprocessing

Approach 3: Two Pointers

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems