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

bro you take substrings in the wrong manner

Because in a substring, we have to take a continuous symbol from a string, but you have taken BA as your substring which is not correct.   

 

---

Repeated question
Option D

---

if substring : n(n+1)/2

if subsequence : 2^n - 1. (2 choice for each letter pick or not pick) except when all not pick length become 0 so remove 1 empty subsequence.

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

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

---

@rahul0521actually there are 2 different terms total substrings and strings of different length and you are calculating strings of different length which is n but for total substring you should count all possible substrings.

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