Problem Overview

You are given two strings s and t. Your task is to determine whether s is a subsequence of t.

A string s is a subsequence of t if all characters of s appear in t in the same order, but not necessarily contiguously.

Example 1:

Input: s = "abc", t = "ahbgdc"
Output: true
Explanation: 'a', 'b', 'c' appear in order in "ahbgdc".

Example 2:

Input: s = "axc", t = "ahbgdc"
Output: false
Explanation: 'x' does not appear after 'a' in sequence.

Constraints:

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

---

Intuition / Approach

This problem is about checking if we can trace all characters of s inside t in the same order.

To solve this efficiently, we can use a two-pointer technique:

• One pointer i traverses string s.
• Another pointer j traverses string t.
• When s[i] == t[j], we move both pointers ahead.
• Otherwise, we move only the pointer j (to keep searching for a match).

If by the end, all characters of s are matched (i.e., i == s.length()), then s is a subsequence of t.

---

Algorithm Steps

1. Initialize two pointers:
   • i = 0 for s
   • j = 0 for t
2. Traverse through t using pointer j:
   • If characters match (s[i] == t[j]), increment both i and j.
   • Otherwise, increment only j.
3. After traversal:
   • If i == s.length(), then every character in s has been found in order → return true.
   • Otherwise, return false.

---

Java Code Implementation

public class IsSubsequence {
    public boolean isSubsequence(String s, String t) {
        int i = 0, j = 0;

        while (i < s.length() && j < t.length()) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }

        return i == s.length();
    }

    public static void main(String[] args) {
        IsSubsequence solution = new IsSubsequence();
        System.out.println(solution.isSubsequence("abc", "ahbgdc")); // true
        System.out.println(solution.isSubsequence("axc", "ahbgdc")); // false
        System.out.println(solution.isSubsequence("", "ahbgdc"));    // true (empty string is always a subsequence)
    }
}

---

Step-by-Step Example

Let’s walk through the example:

s = "abc", t = "ahbgdc"

Step	i (s)	j (t)	s[i]	t[j]	Match?	Action
1	0	0	a	a	Yes	i++, j++
2	1	1	b	h	No	j++
3	1	2	b	b	Yes	i++, j++
4	2	3	c	g	No	j++
5	2	4	c	d	No	j++
6	2	5	c	c	Yes	i++, j++

At the end:
i = 3 == s.length() → true

---

Complexity Analysis

Time Complexity: O(n)

• n is the length of t.
• We traverse through t once while occasionally moving through s.

Space Complexity: O(1)

• We use only two pointers — no additional data structures.

---

Alternative Approach: Dynamic Programming

We can also solve this using DP, similar to the Longest Common Subsequence (LCS) problem.

Define dp[i][j] as whether s[0..i-1] is a subsequence of t[0..j-1].

Recurrence relation:

If s[i-1] == t[j-1]:
    dp[i][j] = dp[i-1][j-1]
Else:
    dp[i][j] = dp[i][j-1]

The final answer is dp[m][n] where m = s.length() and n = t.length().

However, this approach takes O(m * n) time and space — much slower than the two-pointer method, especially since t can be up to 10^4 characters long.

---

Optimized Approach for Multiple s Queries

If we need to check many different s strings against the same t, we can preprocess t into a mapping of character positions using binary search.

Example:

• Precompute indices of each character in t (e.g., for 'a' → [0, 10, 14]).
• For each character in s, find its next valid position using binary search.

This makes it efficient for repeated subsequence checks but is overkill for a single query.