GATE CSE 1998 | Question: 1.23

Question

How many sub strings of different lengths (non-zero) can be formed from a character string of length $n$?

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

Comments

S = {APB}
Possible sub-strings are = {A, P, B, AP, PB, BA, APB}
Go through the options.
Option D:
n(n+1)/2 = 3(3+1)/2 = 6

---

@keshore muralidharan BA is not a sub-string.

---

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 

Answer 1

Assuming in the string of length $n$ provided, all alphabets are distinct.

No. of strings of length $1 = n$
No. of strings of length $2=\left(n-1\right)$
No. of strings of length $3=\left(n-2\right)$
$\vdots$
No. of strings of length $n = 1$

$\begin{align} \text{Hence, total no. of strings} &= n + (n -1) + (n - 2) + (n - 3) +\cdots+ 1\\&= \frac{n(n+1)}{2}\end{align}$

Correct Answer: $D$

Comments

What if subsequence was asked? Then option (C) would be correct with slight modification $2^n-1$ ruling out the possibility of empty subsequence

---

Hi Guys,
Small doubt.
Suppose Sub-string  = ‘ab’       ,ie. |n| = 2
Sub-strings are = ( ε,a,b,ab), but we are excluding non-zero so sub-strings are  = (a,b,ab)
We need strings of ‘different length’ so (a,b) have length 1 and (ab) has 2
So strings of different length are  = 2 i.e  = n
Answers should be n right?
Please let me know if where I’m wrong or there is a gap from my end?
So for max substrings we  are  taking max of strings of diff length but for total we are counting all string ?

---

bro same doubt for me too

what's the actual answer

Answer 2

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


Correct Answer: D

Answer 3

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

Comments

and y ???