Checking if One String is a Subsequence of Another

What is a Subsequence?

Imagine you have a word, and you start crossing out some of its letters. You are not allowed to move any letters around — they must stay in the same order they were before. Whatever letters are left, read from left to right, form a subsequence of the original word.

The key idea is two simple rules:

1. You may remove any letters you want (even none, even almost all of them).
2. You must keep the order of the letters that remain.

For example, take the word abcde:

• ace is a subsequence. Cross out b and d, and the leftover letters a, c, e are still in their original order.
• aec is not a subsequence. Even though all three letters appear in abcde, in the original word c comes before e. Writing them as aec flips their order, which is not allowed.

The Problem

You are given two strings, s and t. You must write a function that returns true if s is a subsequence of t, and false otherwise. In other words: can you build s by deleting some letters from t without rearranging anything?

The function signature looks like this:

bool subsequenceChecker(string s, string t)

Walking Through the Examples

Example 1: s = abc, t = ahbgdc → answer is true.

Let's check it. We try to find each letter of s inside t, moving left to right and never going backwards:

• Find a in t → it is the first letter.
• Now find b *after* that → it appears a bit later.
• Now find c *after* the b → it is the last letter.

We found all of s in order, so abc is a subsequence of ahbgdc.

Example 2: s = coin, t = codeintuition.

Try the same scan: find c, then o after it, then i after that, then n after that. Work through the letters of t and check whether the full word coin can be traced out in order.

The Intuition for Solving It

The natural way to solve this is with two pointers — think of two fingers, one resting on s and one walking across t:

• Put one finger at the start of s and one at the start of t.
• Move the t finger forward one letter at a time.
• Each time the letter under the t finger matches the letter under the s finger, advance the s finger too (that letter is "found").
• Keep going until you reach the end of t.

If the s finger reaches the end of s, it means every letter of s was matched in order, so return true. If you run out of t before finishing s, return false.

This works in one pass over t, which is fast and simple.