Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
17 votes

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}$
in Combinatory
edited by
Anyone please confirm ans ... I am getting option A (n) as correct answer as question is asking for different length substrings.

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


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



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

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

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


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


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

–3 votes

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

and y ???

Related questions

15 votes
1 answer
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$.
asked Sep 26, 2014 in Compiler Design Kathleen 4.2k views
15 votes
3 answers
The number of functions from an $m$ element set to an $n$ element set is $m + n$ $m^n$ $n^m$ $m*n$
asked Sep 26, 2014 in Set Theory & Algebra Kathleen 2.3k views
15 votes
3 answers
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$
asked Sep 26, 2014 in Linear Algebra Kathleen 2.5k views
33 votes
2 answers
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
asked Sep 26, 2014 in Databases Kathleen 4.2k views