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

Lemme know what they actually mean by "different length"? ..according to your answer you are assuming like

# total strings of length1+ # total strings of length2 ...+ #total strings of length n ....

But there are n strings of length 1 (same langth) ,n-1 of length 2 (same length) ....1 string of length n ...so answer can be 'n' in that way...

So what they actually mean..

---

Let string be {a,b,c}

subs of length 2 are ab,bc,ac .how is it then following no of strings of length 2 = n-1.plz clarify

@Digvijay

---

@Gate Mm

if abc is a string, then length 2 sub-strings will be ab,bc only.

---

Because substring is the part of string. So ...ac.... is not part of the string.

---

How to know if all alphabets are distinct? If they are same then we have the option (a) as the answer

---

how ac is not part of substring?

---

$ac$ is a subsequence not a substring.

https://gateoverflow.in/2458/gate1994-1-15

 

---

The answer needs an edit it should be (n-3) in place of (n-2) in summation

---

Questions is talking about "Substring" so adjacent element will be selected everytime...like n element then (n-1) adjacent pair of 2 element and (n-2) adjacent pair of 3 elements...So if you are thinking that select 2 number from n and  "nC2" but in selection we are taking non adjacent pair also

---

Why answer is not 2^n, I am saying that because , say we have n-length string with each character of string we can either take it or leave it, i.e. we have 2 options with each character, hence 2^n,why we are not considering the possibility that the substring obtained may be obtained non-continuously from parent string. 

---

the answer would be $2^{n}$ if they want total subsets possible

and for substring, it will be $n(n+1)/2$

---

Yeah, I realised that later that day,Thanks.

---

for abc → different substrings are

a,b,c,ab,bc,abc =  6 substrings.(Note “ac” is not substring,it is subsequence).

n(n+1)/2 = 3(3+1)/2 = 6 .

---

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 ???