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).

Thinking Process

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).

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
1D DP (this problem) O(n) O(n) or O(1) Linear recurrence
2D DP O(nm) O(nm) or O(n) Grid or two-sequence problems
State machine DP O(n) O(1) Buy/sell, hold/not-hold states
Memoization (top-down) Same as DP O(n) Recursive + cache

Examples

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true
Explanation: "abc" is a subsequence of "ahbgdc" (characters at positions 0, 2, 5).

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: "axc" is not a subsequence of "ahbgdc" because 'x' is not found in "ahbgdc".

Constraints

  • 0 <= s.length <= 100
  • 0 <= t.length <= 10^4
  • s and t consist only of lowercase English letters.

Algorithm Breakdown

Why Two Pointers Work

The two-pointer approach is optimal because:

  1. Order Preservation: We only advance i when we find a match, ensuring order
  2. Greedy Choice: Always match the first occurrence in t (greedy)
  3. Linear Time: Single pass through both strings
  4. Optimal: O(n + m) time complexity

Pointer Movement Logic

  • When characters match (s[i] == t[j]):
    • Advance i (found character in s)
    • Advance j (move past matched character in t)
    • Then advance j again (check next character in t)
  • When characters don’t match (s[i] != t[j]):
    • Keep i unchanged (still looking for this character)
    • Advance j (skip this character in t)

Note: The code increments j twice when there’s a match (once in the if block, once after). This is equivalent to:

if(s[i] == t[j]) {
    i++;
}
j++;  // Always advance j

Subsequence Property

A subsequence maintains the relative order of characters:

  • "ace" is a subsequence of "abcde" (positions 0, 2, 4)
  • "aec" is NOT a subsequence of "abcde" (can’t get ‘e’ before ‘c’)

Time & Space Complexity

  • Time Complexity: O(m) where m is the length of t
    • We iterate through t at most once
    • Pointer i can only advance up to n (length of s)
    • In worst case, we scan all of t
  • Space Complexity: O(1)
    • Only using a few variables
    • No additional data structures

Key Points

  1. Two Pointers: Efficient matching technique
  2. Greedy Matching: Match first occurrence in t
  3. Order Preservation: Characters must appear in same order
  4. Simple Check: All characters matched if i == N
  5. Edge Case: Empty string s is always a subsequence

Common Mistakes

  1. Empty s: s = "" → return true (empty is subsequence of any string)
  2. Empty t: s = "a", t = "" → return false
  3. Same strings: s = "abc", t = "abc" → return true
  4. Single character: s = "a", t = "abc" → return true
  5. No match: s = "x", t = "abc" → return false

  6. Repeated characters: s = "aa", t = "abac" → return true

  7. Wrong pointer logic: Not advancing j when no match
  8. Order violation: Matching characters out of order
  9. Off-by-one: Wrong loop condition or index checking
  10. Empty string: Forgetting that empty string is always subsequence
  11. Not checking all characters: Returning early before checking all of s

Follow-Up: Multiple Queries

If we need to check many strings s against the same t, we can optimize:

// Preprocess t to store character positions
unordered_map<char, vector<int>> charPositions;
for(int i = 0; i < t.length(); i++) {
    charPositions[t[i]].push_back(i);
}

// For each query s, use binary search
bool isSubsequence(string s, unordered_map<char, vector<int>>& pos) {
    int prev = -1;
    for(char c : s) {
        auto it = upper_bound(pos[c].begin(), pos[c].end(), prev);
        if(it == pos[c].end()) return false;
        prev = *it;
    }
    return true;
}

Time: O(m + n log m) per query (better when many queries)

Tags

String, Two Pointers, Greedy, Dynamic Programming, Easy

Key Takeaways

  • Define state: what subproblem does dp[i] (or dp[i][j]) represent?
  • Recurrence: how does the answer build from smaller indices?
  • Base cases first; optimize space if only prior row/layer is needed.

References

Template Reference