The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
2.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}$
asked in Combinatory by Veteran (59.7k points)
edited by | 2.6k views
+1
Anyone please confirm ans ... I am getting option A (n) as correct answer as question is asking for different length substrings.
+8

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

2 Answers

+26 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 - 2) +\cdots+ 1\\&= \frac{n(n+1)}{2}\end{align}$
answered by Veteran (55.6k 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?
–2 votes

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

answered by Loyal (7k points)
0
and y ???
Answer:

Related questions



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

44,150 questions
49,639 answers
163,322 comments
65,808 users