Substring, Subsequence, Prefix, and Suffix

As we begin solving more string problems, we quickly encounter terms such as substring, subsequence, prefix, and suffix. These words appear often in problem statements, and it is important to understand them precisely.

These concepts are related, but they are not the same. A substring must occupy a continuous part of a string. A subsequence only needs to preserve order and does not need to be continuous. A prefix is a substring that starts at the beginning. A suffix is a substring that ends at the end.

These definitions may sound simple at first, but confusing them can lead to incorrect solutions. Let's work through these ideas carefully.

Substring

A substring is a contiguous sequence of characters taken from within a string. Contiguous means the characters must appear consecutively, with no gaps, in the same order they appear in the original.

For the string "hello", some valid substrings are:

Two things are worth noting.

1. A string is a substring of itself.

2. The empty string is a substring of every string.

The key property of a substring is contiguity. The characters must come from consecutive positions. "hlo" is not a substring of "hello" because there are gaps between 'h', 'l', and 'o'. ...