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

Constraints

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

Examples

Example 1:

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

Example 2:

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

Different Approaches

1️⃣ Two Pointers

🔍 Intuition:

Walk through both strings. Try to match characters of s with characters in t one-by-one in order. If all characters in s match in order in t, it's a subsequence.

🧠 Approach:

1. Use two pointers i (for s) and j (for t).
2. Traverse t:
   • If s[i] == t[j], move both pointers.
   • Else move j only.
3. If i reaches the end of s, it's a subsequence.

Code:

// Function to check if string 's' is a subsequence of string 't'
bool isSubsequence(string s, string t) {
    int i = 0, j = 0; // Initialize two pointers: i for 's', j for 't'

    // Loop through both strings while we haven't reached the end of either
    while (i < s.size() && j < t.size()) {
        // If characters at current positions match, move pointer 'i' to next character in 's'
        if (s[i] == t[j]) {
            i++;
        }
        // Always move pointer 'j' to next character in 't'
        j++;
    }

    // If we've checked all characters in 's', then it's a subsequence of 't'
    return i == s.size();
}

Complexity Analysis:

• Time Complexity:O(n), where n = length of t
• Space Complexity:O(1)

2️⃣ Recursion

🔍 Intuition:

Imagine you are standing at two positions:

• i in string s (the subsequence we want to check)
• j in string t (the full string we’re checking against)

You want to move through both strings trying to match the characters of s in order inside t.

• If characters match (s[i] == t[j]), it's a success! Move both pointers.
• If they don’t match, try skipping the current character in t (move only j).

You're basically asking:

"Can I find the next character of s somewhere in the remainder of t?"

If all characters of s are found in this manner, then s is a subsequence of t.

🧠 Approach:

1. Start at i = 0, j = 0
2. Base Cases:
   • If i == s.length(): All characters in s have been matched → return true
   • If j == t.length(): t is exhausted but s isn't → return false
3. If characters match (s[i] == t[j]):
   • Move both i + 1, j + 1
4. If they don’t match:
   • Try to find the match later in t by calling recursive(s, t, i, j + 1)

Code:

class Solution {
public:
    // Helper function to check if s[i..] is a subsequence of t[j..]
    bool recursive(string &s, string &t, int i, int j) {
        // ✅ Base Case 1: If we've matched all characters of s
        if (i >= s.size()) return true;

        // ❌ Base Case 2: If we've reached end of t but s still has characters left
        if (j >= t.size()) return false;

        // If current characters match, move both pointers
        if (s[i] == t[j]) {
            return recursive(s, t, i + 1, j + 1);
        }

        // Else, skip the current character of t and try again
        return recursive(s, t, i, j + 1);
    }

    // Main function to be called from outside
    bool isSubsequence(string s, string t) {
        // Start recursion from beginning of both strings
        return recursive(s, t, 0, 0);
    }
};

Complexity Analysis:

• Time Complexity:O(2^n)
  • Exponential as at every index we have 2 choices.
• Space Complexity:O(n)
  • Recursion stack

3️⃣ Memoization

🔍 Intuition:

The recursive method repeats work because the same (i, j) pair is computed again and again.
So why not remember what result we got for each (i, j) pair?

That’s where memoization comes in — store the result of each (i, j) in a 2D array (or map).

Now if we reach the same (i, j) again, we can just return the cached result instead of recalculating!

🧠 Approach:

1. Create a DP table dp[i][j] where:
   • i = current index in s
   • j = current index in t
   • dp[i][j] = true means s[i..] is a subsequence of t[j..]
2. Base Cases:
   • If i == s.size() → return true
   • If j == t.size() → return false
3. Memo Check:
   • If dp[i][j] != -1, return stored result
4. If match: s[i] == t[j] → store result of recursive(i+1, j+1)
5. Else: store result of recursive(i, j+1)
6. Return dp[i][j]

Code:

class Solution {
public:
    // Memoization table
    vector<vector<int>> dp;

    // Recursive function with memoization
    bool recursive(string &s, string &t, int i, int j) {
        // ✅ Base Case 1: All characters in s matched
        if (i == s.size()) return true;

        // ❌ Base Case 2: t exhausted before s
        if (j == t.size()) return false;

        // 🔁 Check if result already computed
        if (dp[i][j] != -1) return dp[i][j];

        // 🤝 Match characters
        if (s[i] == t[j]) {
            // Store and return result of matching
            return dp[i][j] = recursive(s, t, i + 1, j + 1);
        }

        // ❌ If no match, skip t[j] and try again
        return dp[i][j] = recursive(s, t, i, j + 1);
    }

    // Entry point
    bool isSubsequence(string s, string t) {
        // Initialize memoization table with -1
        dp.resize(s.size() + 1, vector<int>(t.size() + 1, -1));
        return recursive(s, t, 0, 0);
    }
};

Complexity Analysis:

• Time Complexity:O(n * m)
• Space Complexity:O(n * m)
  • Space for the dp array

Follow Up Variant

You’re given:

• A single long string t
• Billions (k ≥ 10⁹) of small strings s₁, s₂, ..., sₖ

You need to efficiently check:

"Is each sᵢ a subsequence of t?"

1️⃣ Preprocessing t once

class Solution {
    unordered_map<char, vector<int>> charPos;

public:
    // Preprocess t
    Solution(string t) {
        for (int i = 0; i < t.size(); ++i) {
            charPos[t[i]].push_back(i);
        }
    }

    // Check if s is a subsequence of t
    bool isSubsequence(string s) {
        int prevIndex = -1;  // Last matched position in t

        for (char c : s) {
            // If char not in t at all
            if (charPos.find(c) == charPos.end()) return false;

            // Find smallest index > prevIndex using binary search
            auto it = upper_bound(charPos[c].begin(), charPos[c].end(), prevIndex);
            if (it == charPos[c].end()) return false;  // No valid next position

            prevIndex = *it;
        }

        return true;
    }
};

Complexity Analysis:

• Time Complexity:
  • Preprocessing t: O(n)
  • Each query si: O(m log f), where f = frequency of char in t
  • Total for k queries: O(k * m log f)
• Space Complexity:O(n)