Is subsequence

Can s be made by deleting some characters of t without reordering the rest? Walk t once and tick off the characters of s in order.

The idea

s is a subsequence of t when its characters appear in t in the same order, with anything in between. Matching greedily is always safe: if s[i] appears at t[j], using this earliest match leaves the most of t for the rest of s. So i only moves on a match, j moves every step, and the answer is whether i reached the end of s.

Code

public bool IsSubsequence(string s, string t) {
    int i = 0, j = 0;
    while (i < s.Length && j < t.Length) {
        if (s[i] == t[j]) i++; // matched: look for the next character of s
        j++; // t's pointer always moves on
    }
    return i == s.Length; // every character of s was matched in order
}

Tips

• Matching the earliest possible character is never worse than waiting for a later one, which is why one pass is enough.
• The loop can stop early: once all of s is matched, the rest of t does not matter.
• Follow-up with many s strings against one t: store the positions of each letter of t and binary search for the next position, O(|s| log |t|) per query.

In the .NET library

string indexing s[i] is O(1) in C#. There is no built-in subsequence check, but the loop is short enough that interviewers expect it written out.