# GATE1998-1.23

17 votes
5.6k 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
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!!

0

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

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

## 2 Answers

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$

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

–3 votes

0
and y ???
Answer:

## Related questions

15 votes
1 answer
1
4.2k views
Let the attribute ‘$val$’ give the value of a binary number generated by $S$ in the following grammar: $S \rightarrow L.L \mid L$ $L \rightarrow LB \mid B$ $B \rightarrow 0 \mid 1$ For example, an input $101.101$ gives $S.val = 5.625$ Construct a syntax directed translation scheme using only synthesized attributes, to determine $S.val$.
15 votes
3 answers
2
2.3k views
The number of functions from an $m$ element set to an $n$ element set is $m + n$ $m^n$ $n^m$ $m*n$
15 votes
3 answers
3
2.5k views
The rank of the matrix given below is: $\begin{bmatrix} 1 &4 &8 &7\\ 0 &0& 3 &0\\ 4 &2& 3 &1\\ 3 &12 &24 &21 \end{bmatrix}$ $3$ $1$ $2$ $4$
33 votes
2 answers
4
4.2k views
There are five records in a database. ... associated with this and it contains the values $1, 3, 2, 5$ and $4$. Which one of the fields is the index built from? Age Name Occupation Category