Is Subsequence

How it works

When checking many strings against the same t, the two-pointer approach becomes inefficient because we scan t repeatedly. Instead, we precompute for each position in t the next occurrence of each character. This lets us jump directly to the next matching character rather than scanning. The preprocessing takes O(26 * m) time and space, but each subsequence query then takes only O(n) time regardless of the length of t.

Steps

1. Build a 2D array store of size m x 26. Entry store[j][c] holds the smallest index >= j where character c appears in t.
2. Fill store from right to left:
   • Initialize store[m-1] with m + 1 for all characters except t[m-1].
   • For each position j from m-2 to 0, copy store[j+1] and update the entry for t[j].
3. To check if s is a subsequence:
   • Start at j = 0.
   • For each character in s, look up its next position from store[j] and jump to it.
   • If the jump goes beyond m, return false.
4. Return true if all characters are matched.

Complexity

• Time complexity: O(n + m)
• Space complexity: O(m)

Where n is the length of the string s and m is the length of the string t.

Things to watch for

Confusing Subsequence with Substring

A subsequence does not require consecutive characters, only that the order is preserved. For example, "ace" is a subsequence of "abcde", but "aec" is not because the order is violated. Make sure to only advance the pointer in s when characters match, not when looking for contiguous matches.

Forgetting to Handle Empty String Cases

When s is empty, it is always a subsequence of any string t (including an empty t). When t is empty but s is not, the answer is always false. Failing to handle these edge cases can lead to index-out-of-bounds errors or incorrect results.

class Solution:
    def isSubsequence(self, s: str, t: str) -> bool:
        n, m = len(s), len(t)
        if m == 0:
            return n == 0

        store = [[m + 1] * 26 for _ in range(m)]
        store[m - 1][ord(t[m - 1]) - ord('a')] = m - 1

        for i in range(m - 2, -1, -1):
            store[i] = store[i + 1][:]
            store[i][ord(t[i]) - ord('a')] = i

        i, j = 0, 0
        while i < n and j < m:
            j = store[j][ord(s[i]) - ord('a')] + 1
            if j > m:
                return False
            i += 1

        return i == n

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int n = s.length(), m = t.length();
        if (m == 0) return n == 0;

        vector<vector<int>> store(m, vector<int>(26, m + 1));
        store[m - 1][t[m - 1] - 'a'] = m - 1;

        for (int i = m - 2; i >= 0; i--) {
            store[i] = store[i + 1];
            store[i][t[i] - 'a'] = i;
        }

        int i = 0, j = 0;
        while (i < n && j < m) {
            j = store[j][s[i] - 'a'] + 1;
            if (j > m) return false;
            i++;
        }

        return i == n;
    }
};