235. Is Subsequence

Scan t left to right with a pointer into s; each time the current character of t matches the next needed character of s, advance in s. If you reach the end of s, every character was found in order.

Idea

s is a subsequence of t when we can find every character of s inside t, in order (gaps allowed). So we greedily march through t once, and whenever the current character of t is exactly the next character of s we still need, we consume it. Being greedy is safe: matching a needed character at the earliest opportunity never blocks a later match, because any solution that skips this occurrence could use it instead.

Algorithm

1. Keep an index i into s, starting at 0 (the next character of s we're looking for).
2. Walk a pointer through every character c of t:
   • If i < len(s) and s[i] == c, we found the next needed character — do i += 1.
3. After scanning all of t, s is a subsequence exactly when i == len(s) (we matched every character of s).

Worked example: s = "abc", t = "ahbgdc"

i reached 3 = len(s), so every character of "abc" was found in order → true.

Complexity

• Time: O(|t|) — a single pass over t.
• Space: O(1) — just the two indices.

class Solution {
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        for (int j = 0; j < t.length(); j++) {
            if (i < s.length() && s.charAt(i) == t.charAt(j)) {
                i++;
            }
        }
        return i == s.length();
    }
}