$\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

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

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