GATE CSE 1989 | Question: 4-i

Question

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.

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$

---

always remember that substring and subsequence are different things.

---

Detailed Video Solution covering All Doubts: https://youtu.be/-QYXpehgNmA 

The same question has come in the GATE exam 3 times.

https://gateoverflow.in/2458/gate-cse-1994-question-1-15 

https://gateoverflow.in/1660/gate-cse-1998-question-1-23 

https://gateoverflow.in/87874/gate-cse-1989-question-4-i 

---

total No. of sub-strings =  zero len + n(n+1)/2

                                     = 1+n(n-1)/2

Answer 1

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].$

Comments

to include the 0 i.e. {} substring.

---

@pavansan

GE can be subsequence not substring.

And 0 length substring means there is no character involved of the given string so only 1 zero length substring.

---

@pavansan

Empty string or 0- length string is a concept of Theory of computation but you don't generally find it in Discrete mathematics books . According to discrete mathematics the number of substrings from character string of length n does not generally include zero length string.But it is fine even if we consider zero length string we will still get marks.

if you have any doubts refer this video https://youtu.be/-QYXpehgNmA?si=0XeYYIXByae6ptj0 

Answer 2

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

Comments

great! this is a new approach here :) thanks for sharing

---

This is smart thinking

Answer 3

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

Answer 4

If you have a string of length n 
Then you’ll have, 

n strings of length 1

n-1 strings of length 2

n-2 strings of length 3

n-4 strings of length 5

.

.

.

.

3 strings of length of n-2

2 strings of length n-1

1 string of length n

 

 Therefore total substrings will be n+(n-1)+(n-2)+(n-3)+........+3+2+1 = n(n+1)/2
_______________________________________________________________________________________________

Example : VARUN HAS LENGTH 5

5 strings of length  1 = {V,A,R,U,N}

4 strings of length  2 = {VA,AR,RU,UN}

3 strings of length  3 = {VAR,ARU,RUN}

2 strings of length  4 = {VARU,ARUN}

1 strings of length  5 = {VARUN}

Therefore total substrings will be 5+(5-1)+(5-2)+(5-3)+(5-4)+(5-5) = 5(5+1)/2 = 15

Answer 5

The correct answer is n⨉(n+1)/2 +1 .

Answer 6

In substring we can't change the relative positions of characters.

So for any string of length n

-> If we have to say we start from 1 length substring then any of the n characters form a substring.

-> If we have to say we now need a 2 length substring then from n substring we will exclude the last character as it can not form any substring. So n-1 character forms the substrings.

-> If 3 characters substring are needed than last 2 characters can not form any substring therefore n-3 characters form a substring.

and similarly till n characters.

So total substrings possible are

n + (n-1) + (n-2) + (n-3) + ... + 1 which is sum of n natural numbers.

And for 0 length substring we need to add 1 also.