What is the brute force approach and complexity for Is Subsequence?

At each matching pair, try both: use t[j] for s[i], or skip t[j] with time complexity O(2^M) and space complexity O(M).

What is the optimal approach and complexity for Is Subsequence?

j walks through t; i moves forward only when s[i] == t[j] with optimal time complexity O(M) and space complexity O(1).

How do you identify the pattern for Is Subsequence?

Look for key signals in the prompt: "subsequence (delete some characters, keep the order)" indicates Gaps are allowed, order is not → walk both strings left to right.; "two strings s and t" indicates One pointer per string: `i` on `s`, `j` on `t`.; "is s inside t (yes/no)" indicates Greedy earliest match; answer is whether `i` reached the end of `s`..

Is Subsequence

Easy·LeetCode #392 Pro OnlyPattern Transfer

LeetCode

Problem Statement

You are given two strings s and t.

Return true if s is a subsequence of t, otherwise false.

s is a subsequence of t if you can get s by deleting some characters of t (maybe none) without changing the order of the characters that remain. For example, "ace" is a subsequence of "abcde", but "aec" is not.

Follow-up: suppose there are a huge number of strings s1, s2, …, sk (say a billion) and you must check each one against the same t. How would you change your approach?

Input

Two strings s and t of lowercase English letters.

Output

true if s is a subsequence of t, else false.

Example 1

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

Output: true

Delete h, g and d from t: a·b·c remain, in order.

Example 2

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

Output: false

t has no x at all, so s can't be formed.

Constraints

• 0 ≤ s.length ≤ 100
• 0 ≤ t.length ≤ 10^4
• s and t contain only lowercase English letters

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“subsequence (delete some characters, keep the order)”

→ Gaps are allowed, order is not → walk both strings left to right.

“two strings s and t”

→ One pointer per string: `i` on `s`, `j` on `t`.

“is s inside t (yes/no)”

→ Greedy earliest match; answer is whether `i` reached the end of `s`.

Approach Complexity Ladder

Brute Force — try every way to match (recursion)O(2^M)O(M)

At each matching pair, try both: use t[j] for s[i], or skip t[j]

Better — dynamic programming tableO(N · M)O(N · M)

dp[i][j] = first i chars of s fit inside the first j chars of t

Optimal — two pointers on two strings (greedy)O(M)O(1)

j walks through t; i moves forward only when s[i] == t[j]

Brute Force Intuition

Write a function tryMatch(i, j) = "can s[i…] be found inside t[j…]?". If s is used up, yes. If t is used up, no. Otherwise, if s[i] == t[j] we may use this character (move both) — and if that fails we also try skipping t[j] (move only j).

Recognition rule for this sub-pattern:

One pointer reads every element, the other marks where the next "kept" element should be written.

Remember this · Two Pointers

Trigger

Sorted array, pairs/triplets with a target, comparing from both ends, compacting an array in place.

Think

If I compare the elements at two positions, can I safely discard one side?

Key question

Which pointer moves, and why can the skipped elements never be the answer?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Two Pointers translate into production architectures and low-level memory mechanics.

LLD Architecture

Circular Buffer & Ring Queue

Two pointer read/write head synchronization in production memory pools.

Explore Track

C++ Internals

Pointers vs References Deep Dive

Pointer arithmetic, dereferencing semantics, and memory layout behind in-place array passes.

Explore Track

C++ Internals

const Correctness & East-Const

Passing read-only spans with const int* without copying buffers.

Explore Track

Remove Duplicates from Sorted Array II