Data Structures Terminology

What you'll learn

• Core Terms

• Substring (Strings Only)

  A substring is a contiguous, in-order slice of a string. Example: For the string "abcdef": - Valid substrings: "abc", "bcd", "cdef", "a", "abcdef", "" - NOT substrings: "ace" (not contiguous), "bac" (wrong order), "xyz" (not present) Num…

• Subarray (Arrays Only)

  A subarray is a contiguous, in-order slice of an array. It's the array analog of substring. Example: For the array [1, 2, 3, 4, 5]: - Valid subarrays: [1, 2, 3], [3, 4], [5], [1, 2, 3, 4, 5], [] - NOT subarrays: [1, 3, 5] (not contiguous…

• Subsequence

  A subsequence is an in-order selection of elements, but NOT necessarily contiguous. You can skip elements, but you cannot rearrange them. Example: For the array [1, 2, 3, 4, 5]: - Valid subsequences: [1, 3, 5], [2, 4], [1, 2, 3, 4, 5], […

• Subset

  A subset is any collection of elements, with no order constraint. Subsets are fundamentally about membership, not position or sequence. Example: For the set {1, 2, 3}: - Valid subsets: {1, 3}, {2}, {1, 2, 3}, {} - Note: {3, 1} and {1, 3}…

• Key Distinctions

  | Term | Order Matters? | Contiguous? | Example from [1,2,3,4,5] | Count for length n | |------|----------------|-------------|---------------------------|-------------------| | Subarray | Yes | Yes | [2, 3, 4] ✓, [1, 3] ✗ | n(n+1)/2 | |…

• When Each Appears in Interviews

• Subarray / Substring Problems

  - "Maximum sum contiguous subarray" (Kadane's algorithm) - "Longest substring without repeating characters" - "Subarray sum equals K" - "Minimum window substring" Pattern: Sliding window, two pointers, prefix sum. ---

• Subsequence Problems

  - "Longest increasing subsequence" (DP) - "Longest common subsequence" (DP) - "Is A a subsequence of B?" (two pointers) - "Count distinct subsequences" Pattern: Dynamic programming, greedy (for special cases). ---

• Subset Problems

  - "Subset sum equals target" (DP / backtracking) - "Generate all subsets (power set)" (backtracking) - "Partition into equal sum subsets" (DP / backtracking) - "K-subset with maximum sum" Pattern: Backtracking, combinatorics, DP. ---

• Common Interview Pitfalls

  1. Confusing subarray with subsequence: - "Find the longest subarray with sum K" ≠ "Find the longest subsequence with sum K" - Subarray: must be contiguous → sliding window, prefix sum. - Subsequence: can skip → DP, greedy. 2. Confusing…

• Visual Summary

  Consider the array [A, B, C]: Subarrays (6 + empty): Subsequences (8 total, including empty): Subsets (8 total, same count but order-agnostic): Note: [A,C] as a subsequence is distinct from [C,A], but as subsets {A,C} = {C,A}. ---

• Additional Terms (To Be Added)

  This page will expand to include: - Prefix / Suffix — leading/trailing portions of a string or array. - Palindrome — reads the same forwards and backwards. - Permutation vs Combination — order matters vs order doesn't. - Contiguous vs No…

• Quiz Yourself

  1. For [1, 2, 3, 4], how many subarrays contain the element 3? Answer: 6 subarrays: [3], [2,3], [3,4], [1,2,3], [2,3,4], [1,2,3,4]. Formula: (index+1) (n-index) = (2+1) (4-2) = 3 2 = 6. 2. For "abc", how many subsequences are there? A…

• Summary

  - Substring / Subarray: Contiguous, in-order → think sliding window, prefix sum. - Subsequence: In-order but can skip → think DP, greedy. - Subset: No order, just membership → think backtracking, combinatorics. Master these distinctions…