What are the differences between subsequences and substrings?

  • 5
    $\begingroup$ the question makes sense to me and has been answered, need it be on hold? $\endgroup$ – Andrew MacFie Apr 17 '15 at 18:16
  • 3
    $\begingroup$ @AndrewMacFie, voted to re-open. $\endgroup$ – goblin Nov 5 '17 at 7:34

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$

  • 1
    $\begingroup$ Voted to re-open. $\endgroup$ – goblin Nov 5 '17 at 8:11

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.