Today we are going to make a comparison of subarray vs substring vs subsequence vs subset. These are all similar concepts but have important differences. For instance, if you have a requirement to write an algorithm to find the subsets of a certain data and you come up with something that only finds the subsequences, you will only be half done. Or in an interview situation, you need to be extra careful about your choice of wording. If a question asks you to return a subsequence and you return a subset, you might fail the interview. Let me start by describing each concept with examples. Finally, I will give you a comparison table.
If you can read the article version of this video at:
• quanticdev.com/algorithms/primitives/subarray-vs-substring-vs-subsequence-vs-subset
My "Algorithms" Playlist for all other algorithm questions & answers:
• kzread.info/head/PLlPRnMzqjADqDZFBqdwzbIjf71h8xYs4x
- - - - - - - - - - -
quanticdev
quantic_dev
quanticdev.com
- - - - - - - - - - -
Abstract:
Subarray
A subarray is a contiguous sequence of elements within an array. For instance, the subarrays of the array {1, 2, 1} would be {1}, {2}, {1, 2}, {2, 1}, {1, 2, 1}, {}. Things to note:
• You can use braces (aka curly brackets) {} or square brackets [] to denote arrays.
• A subarray should be a contiguous subsequence of the parent array. As a result, {1, 1} is not a valid subarray of the array {1, 2, 1}, since {2} in the middle is skipped, so it is not a contiguous subsequence anymore.
• The full array itself is a subarray of itself.
• More details in the video.
Substring
A substring is exactly the same thing as a subarray but in the context of strings. For instance, the substrings of the string "ara" would be "a", "r", "ar", "ra", "ara", "". Things to note:
• A substring is just a subarray that is made up of only characters.
• You can use single ' or double quotes " to denote substrings.
• More details in the video.
Subsequence
Both in mathematics and computer science, a subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements. This means a subsequence is a generalized subarray, where the rule of contiguity does not apply. For instance, the subsequences of the sequence [A, B, A] would be [A], [B], [A, B], [B, A], [A, A], [A, B, A], [].
• In math, it is customary to use angle brackets to denote subsequences. In programming, you can use whatever your programming language uses for arrays and lists.
• Unlike subarrays, subsequences do not need to be contiguous so [A, A] is a perfectly valid subsequence of [A, B, A] whereas it is not a valid subarray.
• More details in the video.
Subset
A set is subset of another set if all its elements are contained by that set. This means, neither contiguity nor ordering of elements matter. For instance, the subsets of the set {1, 2, 3} would be {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}, {}.
• Subsets do not need to be contiguous. {1, 3} is a perfectly valid subset.
• More details in the video.
Comparison
Subarrays and substrings need to be made up of contiguous sequence of elements of their parents, while subsequences and subsets do not have to be. In addition, all of subarrays, substrings and subsequences should preserve element order, meaning their elements should appear in the same order that they appear in their parents, while subsets can have their elements appear in any order.