Difference: Subsequences and Substrings
$\begingroup$

What are the differences between subsequences and substrings?

$\endgroup$
2

1 Answer

$\begingroup$

Substrings are consecutive subsequences. For a $n$-element sequence of pairwise distinct letters you have $n(n+1)/2$ non-empty substrings and $2^n-1$ non-empty subsequences.

For example, for sequence abc we have

  • substrings: a, ab, abc, b, bc, c, and the empty substring;
  • subsequences: a, b, ab, c, ac, bc, abc, and the empty subsequence.

When the letters are repeated, some substrings and subsequences will look the same, however, make sure to check with the definition you were given if the author considers them the same or not.

I hope this helps $\ddot\smile$

$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Chloe Bennett

Chloe Bennett

Culture, Media & Entertainment Columnist

Chloe Bennett explores the intersection of pop culture, streaming entertainment, digital trends, and contemporary lifestyle. Her weekly commentary reaches thousands of culture enthusiasts.

Share this article
Twitter Facebook Pinterest