Substrings and Subsequences

Question

In a string of length n, how many Sub-strings and Sub-sequences can I have... even tho a sub-string is obtained by deleting any prefix and any suffix from s, while a sub-sequence is any string formed by deleting zero or more not necessary a consecutive positions of s.

Answer 1

Assuming you are not ignoring duplicates:

sub strings = n(n+1)/2

count the number of 1 length sub strings = n
count the number of 2 length sub strings = n-1
count the number of 3 length sub strings = n-2
....
count the number of n length sub strings = n - (n-1) = 1

generalizes to the sum of the sequence of numbers from 1 to n.

sub sequences = 2^n

Think of the string as a bit array. either include the character in your sub sequence or do not. there are 2^n combinations.