Question

The number of substrings (of all lengths inclusive) that can be formed from a character string of length n is

• A. n
• B. $n^2$
• C. $\frac{n(n-1)}{2}$
• D. $\frac{n(n+1)}{2}$

Answer 1

The correct option is D $\frac{n(n+1)}{2}$

For a string of length n:

The number of substrings of length 1= n

The number of substrings of length 2= n - 1

The number of substrings of length 3= n -2

and so on....
The number of substrings of length n is 1
So total number of substrings

= n+(n - 1) + ...+ 1
= Sum of n natural numbers
= $\frac{n(n+1)}{2}$