Is Subsequence

Is Subsequence is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Two Pointers pattern, in the Converging (Sorted Array Target Sum) subpattern.

Problem statement

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 <= 104

- s and t consist only of lowercase English letters.

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

Topics and companies

Topics: Two Pointers, String, Dynamic Programming.

Reported in interviews at Bloomberg.

How to practise Is Subsequence on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n), where n is the length of t. We scan through t at most once, and s at most once. time and O(1), as we only use a constant amount of extra space for pointers/counters. space.

Open Is Subsequence in the code editor, or read the Is Subsequence editorial for a worked solution with its approach and complexity analysis.

Where Is Subsequence sits in the DSA pattern sheet

• Two Pointers pattern guide
• Converging (Sorted Array Target Sum) subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Is Subsequence

Other problems that use the same Converging (Sorted Array Target Sum) and Two Pointers techniques:

• Find the Duplicate Number — Medium, same subpattern
• Happy Number — Easy, same subpattern
• Linked List Cycle — Easy, same subpattern
• Backspace String Compare — Easy, same pattern
• Boats to Save People — Medium, same pattern
• Container With Most Water — Medium, same pattern