retagged by
6,801 views
37 votes
37 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.
retagged by

5 Answers

Best answer
49 votes
49 votes

Lets take an example . lets consider the given string is $\text\{GATE\}.$

  • So, set of string of length $1 =\{G,A,T,E\}$ ; cardinality of set $= 4.$
  • Set of strings of length $2 =\{GA,AT,TE\}.$
  • Set of strings of length $3=\{GAT,ATE\}.$
  • Set of strings of length $4 =\{GATE\}.$
  • Set of strings of length $0 =\{\}.$


We cannot have any substring of length $5$ as the given string has only $4$ length.

So total no of substrings possible,

 $=0\;\text{length substring} + 1\;\text{length substrings}+2\;\text{length substrings}+3\;\text{length substrings}+$

      $4\;\text{length substrings}.$

$=\left(1+4+3+2+1\right).$

This means for $1$ length substring to $n$ length substrings, countt will sum of the $n$ natural numbers from $1\;\text{to}\;n .$

$=1+2+3+\ldots+n = \frac{n(n+1)}{2}.$

So total no. of substrings possible $=0\;\text{length strings} + \frac{n(n+1)}{2}= 1+\left[\frac{n(n+1)}{2}\right].$

edited by
1 votes
1 votes
0 length- 1(epsilon)

1 length- n(we can chhioose any bit of string)

2lengh-  n-1 (on the rhs we have n-1 options as we cant take the first letter as it will become 1length substrng and lhs is fixed as substrinng is contiguos)

3 length substring- n-2(same way rhs last  place has n-2 options as first 2 places cant take this place)

simiarly n length substring- 1

so 1+2+3+............n +1= n(n+1)/2 +1
1 votes
1 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

11 votes
11 votes
1 answer
1
makhdoom ghaya asked Nov 30, 2016
7,136 views
For secondary key processing which of the following file organizations is preferred? Give a one line justification:Indexed sequential file organization.Two-way linked lis...
19 votes
19 votes
5 answers
2
31 votes
31 votes
4 answers
3
makhdoom ghaya asked Nov 27, 2016
7,721 views
Which of the following graphs is/are planar?
0 votes
0 votes
0 answers
4