Interview Classic 150 Questions P392 Is Subsequence

---

Timeline

Timeline

2025-10-15

init

Two pointers, dynamic programming

---

Problem:

P392 Is Subsequence

https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

Two pointers

Use two pointers pointing to s and t respectively. If they match, move both pointers forward; if they don’t match, move the pointer pointing to t forward. Note that the empty string needs to be handled separately.

#include <string>
using std::string;

class Solution {
    public:
	bool isSubsequence(string s, string t)
	{
		// Determine whether s is a subsequence of t
		int i = 0, j = 0;
		int s_len = s.size();
		int t_len = t.size();

		if (s_len == 0) {
			return true;
		}
		while (i < s_len && j < t_len) {
			if (s[i] == t[j]) {
				i++;
			}
			j++;
		}
		if (i == s_len && s[i - 1] == t[j - 1]) {
			return true;
		}
		return false;
	}
};

#include <stdio.h>
int main()
{
	Solution solution;
	string s = "abc";
	string t = "ahbgdc";
	printf("%d\n", solution.isSubsequence(s, t));
}

Dynamic Programming

Considering the previous two-pointer approach, we notice that we spend a lot of time finding the next matching character in t. Thus, we can preprocess, for each position in t, the first occurrence position of each character starting from that position. We can use dynamic programming to implement the preprocessing:

Let $f[i][j]$ denote the first occurrence position of character j starting from position i in string t.

For the state transition: if the character at position i in t is exactly j, then $f[i][j]=i$, otherwise j appears starting from position i+1, i.e., $f[i][j]=f[i+1][j]$, so we need to build the dp from back to front.

The state transition equation is:

$$f[i][j] = \begin{cases} i & t[i] = j \\ f[i+1][j] & t[i] \neq j \end{cases}$$

The boundary condition is:

$$f[m][j] = m \quad \forall j \in \{0, 1, \dots, 25\}$$

Where:

• $i$ represents the string $t$ position in (starting from 0, 0 ≤ i ≤ m)
• $j$ denotes the character index (usually ‘a’ corresponds to 0, ‘b’ to 1, …, ‘z’ to 25)
• $f[i][j] = m$ represents that starting from position $i$ onward, the character does not exist $j$

#include <vector>
#include <string>

using std::vector;
using std::string;

class Solution {
    public:
        bool isSubsequence(string s, string t)
        {
                int n = s.size(), m = t.size();
                // m+1 is used to handle boundary cases
                vector<vector<int> > f(m + 1, vector<int>(26, 0));
                for (int i = 0; i < 26; i++) {
                        f[m][i] = m;
                }

                for (int i = m - 1; i >= 0; i--) {
                        for (int j = 0; j < 26; j++) {
                                if (t[i] == j + 'a')
                                        f[i][j] = i;
                                else
                                        f[i][j] = f[i + 1][j];
                        }
                }
                int add = 0;
                for (int i = 0; i < n; i++) {
                        if (f[add][s[i] - 'a'] == m) {
                                return false;
                        }
                        add = f[add][s[i] - 'a'] + 1;
                }
                return true;
        }
};