Difference between Subarray, Subsequence, and Subset

This post will discuss the difference between a subarray, a substring, a subsequence, and a subset.

1. Subarray

A subarray is a slice from a contiguous array (i.e., occupy consecutive positions) and inherently maintains the order of elements. For example, the subarrays of array {1, 2, 3} are {1}, {1, 2}, {1, 2, 3}, {2}, {2, 3}, and {3}.

Please note that there are precisely 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.

code

import java.util.Arrays;
import java.util.List;

class Main
{
    // Function to print all subarrays of the specified array
    public static void printAllSubarrays(List<Integer> input)
    {
        // consider all subarrays starting from `i`
        for (int i = 0; i < input.size(); i++)
        {
            // consider all subarrays ending at `j`
            for (int j = i; j < input.size(); j++)
            {
                // Function to print a subarray formed by [i, j]
                System.out.println(input.subList(i, j + 1));
            }
        }
    }

    public static void main(String[] args)
    {
        List<Integer> input = Arrays.asList(1, 2, 3, 4, 5);
        printAllSubarrays(input);
    }
}

Output:

[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]

2. 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.

For example, the substrings of string ‘apple’ are ‘apple’, ‘appl’, ‘pple’, ‘app’, ‘ppl’, ‘ple’, ‘ap’, ‘pp’, ‘pl’, ‘le’, ‘a’, ‘p’, ‘l’, ‘e’, ‘’.

code

class Main
{
    // Function to print all non-empty substrings of the specified string
    public static void printAllSubstrings(String str)
    {
        int n = str.length();
 
        // consider all substrings starting from `i`
        for (int i = 0; i < n; i++)
        {
            // consider all substrings ending at j
            for (int j = i; j < n; j++) {
                System.out.print("'" + str.substring(i, j + 1) + "', ");
            }
        }
    }
 
    public static void main(String[] args)
    {
        String str = "techie";
        printAllSubstrings(str);
    }
}

Output:

‘t’, ‘te’, ‘tec’, ‘tech’, ‘techi’, ‘techie’, ‘e’, ‘ec’, ‘ech’, ‘echi’, ‘echie’, ‘c’, ‘ch’, ‘chi’, ‘chie’, ‘h’, ‘hi’, ‘hie’, ‘i’, ‘ie’, ‘e’

3. 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. 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 2n-1, where n is the size of the given set.

code

import java.util.ArrayList;
import java.util.List;
 
class Main
{
    // Function to print all subsequences of the specified string
    public static void findPowerSet(String str)
    {
        int n = str.length();
 
        // N stores the total number of subsets
        int N = (int)Math.pow(2, n);
 
        List<String> result = new ArrayList<>();
 
        // generate each subset one by one
        for (int i = 0; i < N; i++)
        {
            StringBuilder sb = new StringBuilder();
 
            // check every bit of `i`
            for (int j = 0; j < n; j++)
            {
                // if j'th bit of `i` is set, print S[j]
                if ((i & (1 << j)) != 0) {
                    sb.append(str.charAt(j));
                }
            }
            result.add("'" + sb.toString() + "'");
        }
 
        System.out.println(result);
    }
 
    public static void main(String[] args)
    {
        String str = "apple";
        findPowerSet(str);
    }
}

Output:

[‘’, ‘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’]

4. 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. 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.

References

• Difference between Subarray, Subsequence, and Subset