Is Subsequence

Is Subsequence

1. What is this problem about?

The Is Subsequence interview question asks you to determine if string s is a subsequence of string t. A subsequence is a new string formed from the original string by deleting some (or no) characters without disturbing the relative positions of the remaining characters. (e.g., "abc" is a subsequence of "ahbgdc").

2. Why is this asked in interviews?

This is a standard question at Apple, Uber, and Microsoft. It tests basic Two Pointers logic and string traversal. For the "Hard" variation (checking multiple s strings against one t), it evaluations your ability to use Pre-processing and binary search to optimize the lookup.

3. Algorithmic pattern used

This problem follows the Two Pointers interview pattern.

1. Initialize: i = 0 (for s), j = 0 (for t).
2. Iterate: While j < t.length:
   • If s[i] == t[j], increment i (you found a match for the next character of the subsequence).
   • Always increment j (to search the rest of the target string).
3. Termination: If i == s.length, all characters of s were found in order.

4. Example explanation

s = "abc", t = "ahbgdc"

1. i=0(a), j=0(a). Match! i=1, j=1.
2. i=1(b), j=1(h). No match. j=2.
3. i=1(b), j=2(b). Match! i=2, j=3.
4. i=2(c), j=3(g). No match. j=4.
5. ... eventually i=3. Return true.

5. Common mistakes candidates make

• Confusing with Substring: Thinking the characters must be contiguous.
• Nested Loops: Using a nested loop to find each character, which is $O(N \cdot M)$ instead of the optimal $O(M)$.
• Extra Space: Creating new strings or using recursion when simple pointers are sufficient.

6. Interview preparation tip