Substring, Subsequence, Prefix, and Suffix
Explore the concepts of substring, subsequence, prefix, and suffix in string manipulation. This lesson helps you understand their precise definitions and differences, enabling you to identify these patterns in problems clearly and implement solutions efficiently using C++ methods.
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 us 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:
Substring | Indices |
"h" | 0 to 0 |
"hel" | 0 to 2 |
"ell" | 1 to 3 |
"llo" | 2 to 4 |
"hello" | 0 to 4 |
"" | any position |
Two things are worth noting:
A string is a substring of itself.
The empty ...