Subarray

  • A subarray is a contiguous slice of an array and inherently maintains the order of elements (i.e., the elements of the subarray occupy consecutive positions). For example, the subarrays of array {1, 2, 3} are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.
  • The following program generates all subarrays of the specified array:
# Function to print all sublists of the specified list
def printallSublists(nums):
    # consider all sublists starting from i
    for i in range(len(nums)):
        # consider all sublists ending at `j`
        for j in range(i, len(nums)):
            # Function to print a sublist formed by [i, j]
            print(nums[i: j + 1])
 
if __name__ == '__main__':
    nums = [1, 2, 3, 4, 5]
    printallSublists(nums)
  • which outputs:
[1]
[1, 2]
[1, 2, 3]
[1, 2, 3, 4]
[1, 2, 3, 4, 5]
[2]
[2, 3]
[2, 3, 4]
[2, 3, 4, 5]
[3]
[3, 4]
[3, 4, 5]
[4]
[4, 5]
[5]
  • Please note that there are precisely \(\frac{n}{(n+1)/2}\) subarrays in an array of size \(n\). Also, there is no such thing as a contiguous subarray. The prefix contiguous is sometimes applied to make the context more clear. So, a contiguous subarray is just another name for a subarray.

Substring

  • A substring of a string s is a string s' that occurs in s. A substring is almost similar to a subarray, but it is in the context of strings (i.e., a substring is a contiguous slice of a string).
  • For example, the substrings of string 'apple' are 'apple', 'appl', 'pple', 'app', 'ppl', 'ple', 'ap', 'pp', 'pl', 'le', 'a', 'p', 'l', 'e', ''.
  • The following program that generates all non-empty substrings of the specified string:
# Function to print all non-empty substrings of the specified string
def printAllSubstrings(s):
    # consider all substrings starting from i
    for i in range(len(s)):
        # consider all substrings ending at j
        for j in range(i, len(s)):
            print(s[i: j + 1], end=' ')
 
if __name__ == '__main__':
    s = 'techie'
    printAllSubstrings(s)
  • which outputs:
t te tec tech techi techie e ec ech echi echie c ch chi chie h hi hie i ie e

Subsequence

  • A subsequence is a sequence that can be derived from another sequence by deleting some elements without changing the order of the remaining elements (i.e., a subsequence maintains the relative order of the array elements). For example, {nums, B, D} is a subsequence of sequence {nums, B, C, D, E} obtained after removing {C} and {E}.
  • People are often confused between a subarray/substring and a subsequence. A subarray or substring will always be contiguous, but a subsequence need not be contiguous. That is, subsequences are not required to occupy consecutive positions within the original sequences. But we can say that both contiguous subsequence and subarray are the same.
  • In other words, the subsequence is a generalization of a substring, or substring is a refinement of the subsequence. For example, {nums, C, E} is a subsequence of {nums, B, C, D, E}, but not a substring, and {nums, B, C} is both a subarray and a subsequence.
  • Please note that a subsequence can be in the context of both arrays and strings. Generating all subsequences of an array/string is equivalent to generating a power set of an array/string. For a given set, S, we can find the power set by generating all binary numbers between \(0\) and \(2^n-1\), where \(n\) is the size of the given set. This approach is demonstrated below:
# Function to print all subsequences of the specified string
def findPowerSet(seq):
    # N stores the total number of subsets
    N = int(pow(2, len(seq)))
 
    # generate each subset one by one
    result = []
    for i in range(N):
        s = ''
        # check every bit of `i`
        for j in range(len(seq)):
            # if j'th bit of `i` is set, print S[j]
            if (i & (1 << j)) != 0:
                s += seq[j]
        result.append(s)
    print(result)
 
if __name__ == '__main__':
    seq = 'apple'
    findPowerSet(seq)
  • which outputs:
['', 'a', 'p', 'ap', 'p', 'ap', 'pp', 'app', 'l', 'al', 'pl', 'apl', 'pl', 'apl', 'ppl', 'appl', 'e', 'ae', 'pe', 'ape', 'pe', 'ape', 'ppe', 'appe', 'le', 'ale', 'ple', 'aple', 'ple', 'aple', 'pple', 'apple']

Subset

  • A subset is any possible combination of the original set. The term subset is often used for subsequence, but that’s not right. A subsequence always maintains the relative order of the array elements (i.e., increasing index), but there is no such restriction on a subset. In other words, a subset is a randomly ordered array which contains elements that exist in the original array. For example, {3, 1} is a valid subset of {1, 2, 3, 4, 5}, but it is neither a subsequence nor a subarray.
  • It is worth noting that all subarrays are subsequences and all subsequences are a subset, but the reverse is not valid. For instance, a subarray {1, 2} of array {1, 2, 3, 4, 5} is also a subsequence and a subset.