in Combinatory retagged by
4,746 views
34 votes
34 votes
How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
in Combinatory retagged by
4.7k views

2 Comments

Reccurrence relation for this problem is

$a_{n} = a_{n-1} + n$ where $a_i, i >= 1$ is numbers of subtrings till $i_{th}$ position of the string with $a_0 = 1$. It's solution is $1+n(n+1)/2$
4
4
edited by

always remember that substring and subsequence are different things.

11
11

5 Answers

0 votes
0 votes

I have different approch .

There are n charaters in string let be 1,2,3…..n
there are (n+1) slots between each string slots are denoted by |
| 1 | 2 | 3 | 4 | ….. | n |
so we need to select any two slot to create substring i.e (n+1)C2
plus add zero string . so answer is
(n+1)C2 + 1
(n+1)*(n)/2 + 1

Related questions