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.

Description Solution Video 8:29

392. Is Subsequence

Easy49.5% acceptance16 companies

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?