Notes

• Subarray: Contiguous segment of an array.
  • [1, 2, 3] in [0, 1, 2, 3, 4]
• Substring: Contiguous segment of a string.
  • "ell" in "hello"
• Subsequence: Sequence derived by deleting some or no elements without changing the order.
  • [1, 3] in [1, 2, 3, 4]
  • "hlo" in "hello"
• Subset: Any combination of elements from a set, order does not matter.
  • {1, 3} in {1, 2, 3}
  • {}, {1, 2}, {3, 2} in {1, 2, 3}

1. Subarray

Definition: A subarray is a contiguous segment of an array. It includes elements that are consecutive in the original array.

Characteristics:

• Must be contiguous.
• Order of elements must be preserved.
• Length can range from 0 to the length of the array.

Example:

• Original Array: [1, 2, 3, 4]
• Possible Subarrays: [1, 2], [2, 3, 4], [3], [1, 2, 3, 4], [] (empty subarray)

2. Substring

Definition: A substring is a contiguous sequence of characters within a string. Like subarrays, substrings consist of consecutive characters.

Characteristics:

• Must be contiguous.
• Order of characters must be preserved.
• Length can range from 0 to the length of the string.

Example:

• Original String: "hello"
• Possible Substrings: "he", "ell", "hello", "o", "" (empty substring)

3. Subsequence

Definition: A subsequence is a sequence derived from another sequence (array or string) by deleting some or no elements without changing the order of the remaining elements.

Characteristics:

• Does not need to be contiguous.
• Order of elements/characters must be preserved.
• Length can range from 0 to the length of the sequence.

Example:

• Original Array: [1, 2, 3, 4]
• Possible Subsequences: [1, 3], [2, 4], [1, 2, 3, 4], [] (empty subsequence)
• Original String: "hello"
• Possible Subsequences: "hlo", "el", "hello", "" (empty subsequence)

4. Subset

Definition: A subset is any combination of elements from a set, where the order does not matter. Subsets include all possible combinations, regardless of order or contiguity.

Characteristics:

• Does not need to be contiguous.
• Order of elements/characters does not matter.
• Length can range from 0 to the length of the set.
• Includes all possible combinations of the elements.

Example:

• Original Set: {1, 2, 3}
• Possible Subsets: {}, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}