3.7k views

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

1. $n$
2. $n^2$
3. $2^n$
4. $\frac{n(n+1)}{2}$

edited | 3.7k views
+2
Anyone please confirm ans ... I am getting option A (n) as correct answer as question is asking for different length substrings.
+12

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

0

^ what do you mean by - strings of different lengths (non-zero)  ??

+1

^

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
Okay, thanks:)
0
why is substring different from subsets?
+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?
0
..
0
yes,i  am also getting n as(a,ab,abc)  as they are of different length?? but why answer is d??
0
If we don't consider null as a string then it total substring = [{n(n+1)}/2 ]
So correct option D

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$
by Veteran (60.8k points)
edited by
+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

+3
@Gate Mm

if abc is a string, then length 2 sub-strings will be ab,bc only.
+2
Because substring is the part of string. So ...ac.... is not part of the string.
0
How to know if all alphabets are distinct? If they are same then we have the option (a) as the answer
0
how ac is not part of substring?
0

$ac$ is a subsequence not a substring.

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

+1
The answer needs an edit it should be (n-3) in place of (n-2) in summation
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

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

by Loyal (8k points)
0
and y ???