7. Is Subsequence
🔗 LeetCode Problem: 392. Is Subsequence
📊 Difficulty: Easy
🏷️ Topics: Two Pointers, String, Dynamic Programming
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
Explanation: "abc" is a subsequence of "ahbgdc"
Example 2:
Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: "axc" is NOT a subsequence of "ahbgdc"
Constraints:
- 0 <= s.length <= 100
- 0 <= t.length <= 10^4
- s and t consist only of lowercase English letters
Follow-up: If there are lots of incoming s strings (say 1 billion), how would you optimize checking each one?
🎨 Visual Understanding
The Problem Visualized
Input: s = "abc", t = "ahbgdc"
String t: a h b g d c
↓ ↓ ↓
String s: a b c
Match process:
Step 1: Look for 'a' in t → Found at index 0 ✓
Step 2: Look for 'b' in t (after index 0) → Found at index 2 ✓
Step 3: Look for 'c' in t (after index 2) → Found at index 5 ✓
All characters of s found in order → true
Input: s = "axc", t = "ahbgdc"
String t: a h b g d c
↓ ? ↓
String s: a x c
Match process:
Step 1: Look for 'a' in t → Found at index 0 ✓
Step 2: Look for 'x' in t (after index 0) → NOT FOUND ✗
Cannot find 'x' in t → false
Subsequence vs Substring vs Subarray
Key Difference:
Subsequence: Can skip characters, order MUST be preserved
"ace" is subsequence of "abcde"
a_c_e (skipped b and d, kept order)
Substring: Must be contiguous characters
"bcd" is substring of "abcde"
Cannot skip characters
Examples with "abcde":
✓ Subsequences: "a", "ac", "ace", "bde", "e", "abcde"
✓ Substrings: "abc", "bcd", "cde", "abcde"
✗ Not subsequence: "aec" (wrong order), "xyz" (not in string)
Two Pointer Technique Visualization
s = "abc"
t = "ahbgdc"
Initial:
s: a b c
↑
i=0
t: a h b g d c
↑
j=0
Step 1: s[0]='a', t[0]='a' → Match!
i → 1, j → 1
Step 2: s[1]='b', t[1]='h' → No match
i stays 1, j → 2
Step 3: s[1]='b', t[2]='b' → Match!
i → 2, j → 3
Step 4: s[2]='c', t[3]='g' → No match
i stays 2, j → 4
Step 5: s[2]='c', t[4]='d' → No match
i stays 2, j → 5
Step 6: s[2]='c', t[5]='c' → Match!
i → 3, j → 6
Final: i = 3 = s.length() → All matched ✓
🎯 Approach 1: Two Pointers (Optimal)
The Most Natural Thinking 💭
Core Logic:
Use two pointers:
- Pointer i for string s (what we're looking for)
- Pointer j for string t (where we're searching)
Strategy:
- Scan through t with pointer j
- When t[j] matches s[i], move i forward
- Always move j forward
- If i reaches end of s → found all characters!
Why This Works: - Greedy approach: match characters as soon as we find them - Order is preserved (j only moves forward) - Single pass through both strings - No backtracking needed
Key Insight: - We don't need to find all possible subsequences - Just need to verify if s CAN be formed from t - Match first occurrence greedily
Implementation
public boolean isSubsequence(String s, String t) {
int i = 0; // Pointer for s
int j = 0; // Pointer for t
// Scan through t, matching characters from s
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++; // Found match, move to next char in s
}
j++; // Always move forward in t
}
// If we matched all characters in s, i should equal s.length()
return i == s.length();
}
Step-by-Step Execution: s = "abc", t = "ahbgdc"
Initial State:
═══════════════════════════════════════════════════════════════════
s = "abc" (length 3)
t = "ahbgdc" (length 6)
i = 0 (looking for 'a')
j = 0 (at 'a' in t)
═══════════════════════════════════════════════════════════════════
Iteration 1:
├─ i=0, j=0
├─ s[0]='a', t[0]='a'
├─ Match found! ✓
├─ i++ → i=1
└─ j++ → j=1
State: Looking for 'b', at 'h' in t
Iteration 2:
├─ i=1, j=1
├─ s[1]='b', t[1]='h'
├─ No match
├─ i stays 1
└─ j++ → j=2
State: Still looking for 'b', at 'b' in t
Iteration 3:
├─ i=1, j=2
├─ s[1]='b', t[2]='b'
├─ Match found! ✓
├─ i++ → i=2
└─ j++ → j=3
State: Looking for 'c', at 'g' in t
Iteration 4:
├─ i=2, j=3
├─ s[2]='c', t[3]='g'
├─ No match
├─ i stays 2
└─ j++ → j=4
State: Still looking for 'c', at 'd' in t
Iteration 5:
├─ i=2, j=4
├─ s[2]='c', t[4]='d'
├─ No match
├─ i stays 2
└─ j++ → j=5
State: Still looking for 'c', at 'c' in t
Iteration 6:
├─ i=2, j=5
├─ s[2]='c', t[5]='c'
├─ Match found! ✓
├─ i++ → i=3
└─ j++ → j=6
State: i=3 equals s.length()=3
Loop exits: j=6 equals t.length()=6
Final Check:
i == s.length() → 3 == 3 → true
═══════════════════════════════════════════════════════════════════
🎯 RESULT: true
═══════════════════════════════════════════════════════════════════
Another Example: s = "axc", t = "ahbgdc"
Iteration 1:
i=0, j=0: 'a'=='a' ✓ → i=1, j=1
Iteration 2:
i=1, j=1: 'x'!='h' → i=1, j=2
Iteration 3:
i=1, j=2: 'x'!='b' → i=1, j=3
Iteration 4:
i=1, j=3: 'x'!='g' → i=1, j=4
Iteration 5:
i=1, j=4: 'x'!='d' → i=1, j=5
Iteration 6:
i=1, j=5: 'x'!='c' → i=1, j=6
Loop exits: j=6 equals t.length()
Final: i=1, s.length()=3
i != s.length() → false
Result: false (never found 'x' in t)
⏰ Time: O(n) where n = length of t (single pass)
💾 Space: O(1) - only two pointers
🎯 Approach 2: Recursive
Thought Process 💭
Core Logic:
Recursive definition:
isSubsequence(s, t) =
If s is empty → true (empty is subsequence of anything)
If t is empty → false (non-empty s can't be in empty t)
If s[0] == t[0] → check rest: isSubsequence(s[1:], t[1:])
If s[0] != t[0] → skip t[0]: isSubsequence(s, t[1:])
Why This Works: - Base cases handle empty strings - If first chars match, check remaining strings - If don't match, advance in t only (skip character) - Naturally preserves order
Trade-off: - More intuitive for some people - Uses call stack (O(n) space) - Slower due to function call overhead
Implementation
public boolean isSubsequence(String s, String t) {
return isSubsequenceHelper(s, t, 0, 0);
}
private boolean isSubsequenceHelper(String s, String t, int i, int j) {
// Base case: matched all characters in s
if (i == s.length()) {
return true;
}
// Base case: ran out of characters in t
if (j == t.length()) {
return false;
}
// If characters match, move both pointers
if (s.charAt(i) == t.charAt(j)) {
return isSubsequenceHelper(s, t, i + 1, j + 1);
}
// If don't match, move only t pointer
return isSubsequenceHelper(s, t, i, j + 1);
}
Recursion Tree: s = "abc", t = "ahbgdc"
isSubsequence("abc", "ahbgdc", 0, 0)
├─ 'a'=='a' ✓
└─ isSubsequence("abc", "ahbgdc", 1, 1)
├─ 'b'!='h'
└─ isSubsequence("abc", "ahbgdc", 1, 2)
├─ 'b'=='b' ✓
└─ isSubsequence("abc", "ahbgdc", 2, 3)
├─ 'c'!='g'
└─ isSubsequence("abc", "ahbgdc", 2, 4)
├─ 'c'!='d'
└─ isSubsequence("abc", "ahbgdc", 2, 5)
├─ 'c'=='c' ✓
└─ isSubsequence("abc", "ahbgdc", 3, 6)
└─ i==3 equals s.length() → return true
Result: true
⏰ Time: O(n) where n = length of t
💾 Space: O(n) - recursion call stack
🎯 Follow-up: Optimizing for Many Queries
The Challenge 💭
Problem:
If we have 1 billion strings s to check against same t:
- Current approach: O(n) per query
- Total: O(billion × n) - too slow!
Need: Preprocess t once, then O(log n) or O(1) per query
Solution: Binary Search with Preprocessing
Core Logic:
Preprocessing (once):
1. Build index map: For each character, store all positions in t
Example: t = "ahbgdc"
Index map: {
'a': [0],
'h': [1],
'b': [2],
'g': [3],
'd': [4],
'c': [5]
}
Query (for each s):
1. Start with position -1
2. For each char in s:
- Find next occurrence in index map after current position
- Use binary search on the list
- If not found → return false
3. Return true if all chars found
Implementation
class Solution {
// Preprocessing: build index map
private Map<Character, List<Integer>> buildIndex(String t) {
Map<Character, List<Integer>> index = new HashMap<>();
for (int i = 0; i < t.length(); i++) {
char c = t.charAt(i);
index.putIfAbsent(c, new ArrayList<>());
index.get(c).add(i);
}
return index;
}
// Binary search to find next occurrence after prevPos
private int findNextPos(List<Integer> positions, int prevPos) {
int left = 0, right = positions.size() - 1;
int result = -1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (positions.get(mid) > prevPos) {
result = positions.get(mid);
right = mid - 1; // Try to find earlier position
} else {
left = mid + 1;
}
}
return result;
}
public boolean isSubsequence(String s, String t) {
// Preprocess t
Map<Character, List<Integer>> index = buildIndex(t);
int currentPos = -1;
for (char c : s.toCharArray()) {
if (!index.containsKey(c)) {
return false; // Character not in t
}
// Find next occurrence after currentPos
int nextPos = findNextPos(index.get(c), currentPos);
if (nextPos == -1) {
return false; // No occurrence after currentPos
}
currentPos = nextPos;
}
return true;
}
}
Complexity Analysis
Preprocessing:
Time: O(n) where n = length of t
Space: O(n) to store index map
Per Query:
Time: O(m log n) where m = length of s
- For each char in s: binary search on list
Space: O(1) per query
For 1 billion queries:
Without preprocessing: O(billion × n)
With preprocessing: O(n) + O(billion × m log n)
If m << n and log n is small, huge improvement!
🔍 Edge Cases
Case 1: Empty s
Input: s = "", t = "abc"
Output: true
Reason: Empty string is subsequence of any string
Case 2: Empty t
Input: s = "abc", t = ""
Output: false
Reason: Non-empty s can't be subsequence of empty t
Case 3: Both empty
Input: s = "", t = ""
Output: true
Case 4: s equals t
Input: s = "abc", t = "abc"
Output: true
Case 5: s longer than t
Input: s = "abcd", t = "abc"
Output: false
Case 6: Single character match
Input: s = "b", t = "abc"
Output: true
Case 7: Single character no match
Input: s = "x", t = "abc"
Output: false
Case 8: All characters same
Input: s = "aaa", t = "aaaa"
Output: true
Case 9: Repeated characters in wrong order
Input: s = "aab", t = "aabaa"
Output: true
Reason: Can pick 'a' at 0, 'a' at 1, 'b' at 2
Common Mistakes
Mistake 1: Not handling empty strings
❌ Wrong: Assume both strings are non-empty
✓ Right: Check if s is empty (return true)
Mistake 2: Resetting j pointer
❌ Wrong: j = 0 after each match
✓ Right: j only moves forward, never resets
Mistake 3: Breaking on first mismatch
❌ Wrong: return false when characters don't match
✓ Right: Continue scanning t, only increment i on match
Mistake 4: Confusing with substring problem
❌ Wrong: Look for contiguous characters
✓ Right: Characters can be non-contiguous (can skip)
Mistake 5: Wrong final condition
❌ Wrong: return j == t.length()
✓ Right: return i == s.length()
🎯 Key Takeaways
⚡ Algorithm Comparison
Approach 1: Two Pointers (BEST)
Time: O(n)
Space: O(1)
Use: Default choice
Approach 2: Recursion
Time: O(n)
Space: O(n) - call stack
Use: When recursion preferred
Follow-up: Binary Search + Preprocessing
Preprocess: O(n) time, O(n) space
Per query: O(m log n)
Use: Many queries on same t
🔑 The Core Insight
Subsequence ≠ Substring
- Subsequence: Can skip characters, order matters
- Substring: Must be contiguous
Two Pointer Pattern:
- Pointer i: What we're looking for (s)
- Pointer j: Where we're searching (t)
- Match greedily: take first occurrence
- Only move i when match found
- Always move j forward
🎯 Pattern Recognition
Problem Type: Subsequence Matching
Core Pattern: Two Pointers (one for each string)
When to Apply:
✓ Checking if one sequence is in another
✓ Order matters but gaps allowed
✓ Greedy matching works
✓ Single pass possible
Key Technique:
→ Greedy approach (match first occurrence)
→ Two pointers moving forward
→ No backtracking needed
Related Problems:
- Number of Matching Subsequences (LC 792)
- Is Subsequence (follow-up with preprocessing)
- Longest Common Subsequence (LC 1143)
- Shortest Common Supersequence (LC 1092)
🧠 Interview Strategy
Step 1: "Need to check if s appears in t preserving order"
Step 2: "Can use two pointers - one for each string"
Step 3: "Match characters greedily, advance t always"
Step 4: "Success if we match all of s"
Step 5: "For follow-up: preprocess t, use binary search"
📝 Quick Revision Notes
🎯 Core Concept:
Use two pointers to scan through both strings. Match characters from s in t while preserving order. Advance pointer in s only on match, always advance pointer in t.
⚡ Quick Implementation:
public boolean isSubsequence(String s, String t) {
int i = 0, j = 0;
while (i < s.length() && j < t.length()) {
if (s.charAt(i) == t.charAt(j)) {
i++; // Found match
}
j++; // Always advance in t
}
return i == s.length(); // Matched all of s?
}
🔑 Key Insights:
- Greedy matching works (take first occurrence)
- Two pointers scan both strings simultaneously
- i advances only on match, j always advances
- Order preserved because j never goes backward
- Empty s is always valid subsequence
🎪 Memory Aid:
"Walk through t, pick characters for s as you find them!"
Think: "i = what I want, j = where I am looking"
Related Patterns
- Number of Matching Subsequences (LC 792)
- Longest Common Subsequence (LC 1143)
- Minimum Window Subsequence (LC 727)
Happy practicing! 🎯