Skip to main content

5 posts tagged with "associative"

View All Tags

· 2 min read
Sarthak Mohanty
  • A subarray is a contiguous part of array and maintains relative ordering of elements. For an array/string of size n, there are n*(n+1)/2 non-empty subarrays/substrings.
  • A subsequence maintain relative ordering of elements but MAY or MAY NOT be a contiguous part of an array. For a sequence of size n, we can have 2^n-1 non-empty sub-sequences in total.
  • A subset MAY NOT maintain relative ordering of elements and can or cannot be a contiguous part of an array. For a set of size n, we can have (2^n) sub-sets in total.
caution

  • Every Subarray is a Subsequence.

  • Every Subsequence is a Subset.

  • ehen we find subset of a set we dont take a subset which is a premutation

    • example {1,2,3}:
      • {2,1} and {1,2} are the same thing that is {2,1} is permutation of {1,2} , so we count it only once

To add to this there is usually a confusion with substrings. A substring is exactly the same thing as a subarray but in the context of strings.

Consider an array: array = [1,2,3,4]

  • Subarray : [1,2],[1,2,3] - is continous and maintains relative order of elements
  • Subsequence: [1,2,4] - is not continous but maintains relative order of elements
  • Subset: [1,3,2] - is not continous and does not maintain relative order of elements. All its permutations are also valid but only one set of these permulations can be counted once.