17 votes

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

- $n$
- $n^2$
- $2^n$
- $\frac{n(n+1)}{2}$

3

Anyone please confirm ans ... I am getting option A (n) as correct answer as question is asking for different length substrings.

15

**Aswer will be D** (asuming all **characters** in string are **distinct**)

Take an example String **"abc"**

**Substrings** of **length 1** = **{a,b,c}**

**Substrings** of **length 2** = **{ab,bc}**

**Substrings** of **length 3** = **{abc}**

**Total Substrings of non zero length** will be **3+2+1 = 6**

However **Answer will be A**, if all **characters are same**

consider **"aaa"**

**Substrings** of **length 1** = **{a}**

**Substrings** of **length 2** = **{aa}**

**Substrings** of **length 3** = **{aaa}**

So answer can be vary from n to $\frac{n(n+1)}{2}$ if the distinct keyword is not given!!

2

^

**strings of different lengths (non-zero)**

means some string are of length 1

Some string lengh 2

................some string length n

it doesnot mean each string of different length

1

So some substrings will be of length 1, some of length 2 and so on. Since it is mentioned how many substrings of different length, from each set we take one substring i.e. one substring of length 1, one substring of length 2 and so on till one substring of length n. Thus, total substrings of different length possible are n. What is wrong with this reasoning?

35 votes

Best answer

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$

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$

1

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

0

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

0

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

0

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

0

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.