Subarrays/SubString vs Subsequence vs Subsets
SUBARRAY :
1 min readOct 3, 2022
A subarray is a contiguous part of an array and maintains the relative ordering of elements. For an array/string of size n, there are n*(n+1)/2 non-empty subarrays/substrings.
SUBSEQUENCE :
A subsequence maintains relative ordering of elements but may or may not be a contiguous part of an array. For a sequence of size n, we can have 2^n-1 non-empty sub-sequences in total.
SUBSET :
A subset MAY NOT maintain the relative ordering of elements and can or cannot be a contiguous part of an array. For a set of size n, we can have (2^n) sub-sets in total.
Consider an array:
array = [1,2,3,4]
- Subarray : [1,2],[1,2,3] — is continuous and maintains relative order of elements
- Subsequence: [1,2,4] — is not continuous but maintains relative order of elements
- Subset: [1,3,2] — is not continuous and does not maintain the relative order of elements
Some interesting observations :
- Every Subarray is a Subsequence.
- Every Subsequence is a Subset.