How do you solve Is Subsequence?

Initialize two pointers i and j at 0. While both pointers are within their string lengths, compare s[i] and t[j]. If they match, increment i. Always increment j. After the loop, if i equals the length of s, return true; otherwise, false.

Is Subsequence

Q: What is the time complexity of Is Subsequence?

O(n). Each pointer advances at most the length of its respective string. The pointer j scans t once, and i scans s at most once, resulting in linear time.

Q: What pattern does Is Subsequence use?

The Pattern: Two Pointers (Linear Scan for Subsequence) The Heuristic: When checking if one sequence is a subsequence of another, use two pointers to scan both sequences simultaneously, advancing the subsequence pointer only on matches and the main sequence pointer always, ensuring O(n) time.

Easy Two Pointers

Problem

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

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

Example

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

Output: true

The algorithm uses two pointers to scan both strings. Starting at the beginning, it compares characters s[i] and t[j]. When characters match, it advances the pointer i in s to look for the next character. The pointer j in t always advances. For the input, s[0] = 'a' matches t[0] = 'a', so i moves to 1. Then s[1] = 'b' matches t[2] = 'b', so i moves to 2. Finally, s[2] = 'c' matches t[5] = 'c', so i moves to 3, which equals len(s), indicating all characters were found in order. The function returns true.

Approach

Straightforward Solution

A brute-force approach would try all subsequences of t and check if any equals s, which is exponential and infeasible for large inputs.

Core Observation

A subsequence requires characters of s to appear in t in order, but not necessarily contiguously. This means we can scan both strings linearly, advancing through t and only advancing through s when a matching character is found.

Path to Optimal

The key insight is to use two pointers: one for s and one for t. By advancing the pointer in t at every step and only advancing the pointer in s when characters match, the algorithm efficiently checks if s is a subsequence of t in a single pass.

Optimal Approach

Preview

Initialize two pointers i and j at 0. While both pointers are within their string lengths, compare s[i] and t[j]…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

Each pointer advances at most the length of its respective string. The pointer j scans t once, and i scans s at most once, resulting in linear time.

Space

O(1)

Only a fixed number of integer pointers are used, with no additional data structures proportional to input size.

Pattern Spotlight

Two Pointers (Linear Scan for Subsequence)

When checking if one sequence is a subsequence of another, use two pointers to scan both sequences simultaneously, advancing the subsequence pointer only on matches and the main sequence pointer always, ensuring O(n) time.

Solution

Python

1class Solution:
  def isSubsequence(self, s: str, t: str) -> bool:
      i = j = 0
      while i < len(s) and j < len(t):
          if s[i] == t[j]:
              i += 1
          j += 1
8
      return i == len(s)

Step-by-Step Solution

Traverse Both Strings with Two Pointers to Identify Subsequence

3i = j = 0
4while i < len(s) and j < len(t):
5    if s[i] == t[j]:
6        i += 1
7    j += 1

Objective

To iterate through both strings simultaneously, advancing the subsequence pointer only when matching characters are found.

Key Insight

By maintaining two pointers, the algorithm efficiently checks for the presence of s as a subsequence in t without backtracking or nested loops. The pointer j always moves forward, ensuring linear time, while pointer i only moves forward when a matching character is found, preserving order.

Interview Quick-Check

Core Logic

Two pointers scan s and t; pointer i advances only on matches, pointer j always advances, ensuring O(n) time subsequence check.

State & Boundaries

The loop continues while both pointers are within their string lengths, ensuring all characters are checked.

Common Pitfalls & Bugs

Advancing pointer i regardless of match would break the subsequence order requirement.

Return True if All Characters of s are Matched in t

To determine if the entire string s was found as a subsequence within t.

1 more step with full analysis available on Pro.

Line Analysis

This solution has 2 Critical lines interviewers watch for.

Line 9 Critical

return i == len(s)

Return true if all characters in s were matched; otherwise, false.

If i equals the length of s, it confirms that every character in s was found in order within t, satisfying the subsequence condition.

Line 6 Critical

i += 1

Advance pointer i when characters match.

Advancing i only on matches preserves the order of characters in s, ensuring the subsequence property is maintained.

Full line-by-line criticality + rationale for all 6 lines available on Pro.

Test Your Understanding

Why does advancing the pointer in s only on character matches guarantee correctness?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Is Subsequence from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Is Subsequence drill

or drill a free problem

1	`class Solution:`
2	`def isSubsequence(self, s: str, t: str) -> bool:`
3	`i = j = 0`
4	`while i < len(s) and j < len(t):`
5	`if s[i] == t[j]:`
6	`i += 1`
7	`j += 1`
8
9	`return i == len(s)`

3	`i = j = 0`
4	`while i < len(s) and j < len(t):`
5	`if s[i] == t[j]:`
6	`i += 1`
7	`j += 1`