Data Structures Basics

Very often you encounter the terms substring,subarrays, subset and subsequence in general software development cycle or may be in a Technical Interview discussions asking the candidate to pull out a specific subset or subsequence or substring or subset. This article explains you these concepts along with an executed code to support the basic use case.

Before delving into further , you must know what is contiguous and order Preserved.

Contiguous means that the elements are adjacent to each other with no gaps in between. In the context of arrays or sequences, it means that the elements are consecutive and directly follow one another without any interruption.

Order preserved means that the elements appear in the same relative order as they do in the original sequence, even if there are gaps between them. In other words, when creating a subsequence, you can remove elements, but the remaining elements must appear in the same order as they did in the original sequence.

Now, lets get to the basics and define the core concepts of this article.

Subsequence: A subsequence maintains the same order of elements as the original array, but it can skip elements.

Substring / Subarray: A subarray is a contiguous sequence of elements from the original array.

Subset: A subset is any collection of elements (including duplicates) from the original set, regardless of order.

Example 1 Now lets start , take an example of an array A =["Rakesh"]. Here you can expect the various probabilities of picking as substring like "akesh" , "ak" , "Rakesh", "esh", "es", "e" . This is non numeric i.e string

Example 2 Given the array [1, 4, 8, 2, 6, 1, 3], find and Mark what the below values correspond to.

[1, 4, 2] [4, 8, 2] [6, 2, 3]

[1, 4, 2]

• Subsequence: Yes, because [1, 4, 2] appears in the same order in the original array, though not necessarily contiguously.
• Subarray: No, because the elements [1, 4, 2] are not contiguous in the original array.
• Subset: Yes, because it consists of elements present in the original array, regardless of order or contiguity.

[4, 8, 2]

• Subsequence: Yes, because [4, 8, 2] appears in the same order as in the original array.
• Subarray: Yes, because [4, 8, 2] is contiguous in the original array.
• Subset: Yes, because all elements [4, 8, 2] are present in the original array, and order does not matter for subsets

[6,2,3]

• Subsequence: No, because [6, 2, 3] does not appear in the same order as in the original array (2 appears before 6 in the original array).
• Subarray: No, because [6, 2, 3] is not contiguous in the original array.
• Subset: Yes, because all elements [6, 2, 3] are present in the original array, and order does not matter for subsets.

Summary :

Some Notes to Ponder:

• Every Subarray is a Subsequence.
• Every Subsequence is a Subset.

Lets find a simple subArray from the main Array!!

function isSubarray(mainArray, subArray) {
    const n = mainArray.length; // Length of mainArray
    const m = subArray.length; // Length of subArray

    // Loop through mainArray only up to the point where subArray can fit
    for (let i = 0; i <= n - m; i++) {
        let j;
        // Check if subArray matches starting from index i
        for (j = 0; j < m; j++) {
            if (mainArray[i + j] !== subArray[j]) {
                break; // If any element does not match, break out of the inner loop
            }
        }
        // If we completed the inner loop, subArray is found
        if (j === m) {
            return true;
        }
    }
    return false; // Return false if subArray is not found
}

// Example usage:
const mainArray = [1, 4, 8, 2, 6, 1, 3];
const subArray1 = [4, 8, 2];
const subArray2 = [1, 4, 2];

console.log(isSubarray(mainArray, subArray1)); // true
console.log(isSubarray(mainArray, subArray2)); // false        

Major Points to be Noted from the above written code

• Condition i <= n - m: This condition ensures that there are enough remaining elements in mainArray starting from index i to match the entire subArray.
• If i were to go beyond n - m, then starting a subarray match at it would mean that there wouldn't be enough elements left in mainArray to complete the comparison with subArray.
• For example, if mainArray has 7 elements (n = 7), and subArray has 3 elements (m = 3), then the last valid starting index in mainArray to match subArray would be 4 (n - m = 4), because mainArray[4] to mainArray[6] gives us 3 elements.
• The inner loop checks each element of subArray against the corresponding element in the segment of mainArray starting at index i. If all elements match, the loop completes and j reaches m. If any element does not match, the loop breaks early

Hope This gives you a starter on sub-atomic modules of an large Array and how to rip it apart to get many combinations of the output. Well I am also giving you some DSA questions and with the solutions where the underlying base revolves around this topic.

Common Questions on DSA on this concepts:

1. Check if a repeated subsequence is present in a string or not
2. Check if a set of moves is circular or not
3. Isomorphic Strings
4. Find all words from the given list that follow the same order of characters as the given pattern
5. Longest Palindromic Substring Problem
6. Find the longest substring of a string containing distinct characters
7. Group anagrams together from a list of words
8. Remove all extra spaces from a string
9. Reverse a string using recursion
10. Longest Common Subsequence Problem
11. Shortest Common Supersequence Problem
12. Check if a string matches with the given wildcard pattern
13. Find the shortest unique prefix for every word in an array