The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+11 votes
1.3k views

The number of substrings (of all lengths inclusive) that can be formed from a character string of length $n$ is

  1. $n$
  2. $n^2$
  3. $\frac{n(n-1)}{2}$
  4. $\frac{n(n+1)}{2}$
asked in Combinatory by Veteran (59.5k points)
edited by | 1.3k views

2 Answers

+16 votes
Best answer
no. of substrings of length $n$ is $1$.

no. of substrings of length $(n-1)$ is $2$.

no. of substrings of length $(n-2)$ is $3$.

so $\frac{n(n+1)}{2}$.
answered by Boss (14.3k points)
edited by
+4
Yes. And 2^n if we could have changed the order of characters.
+6
^^ shouldn't be some assumption regarding n(n+1)/2.

1. All character of length n should be distinct.

2. Null string also der i.e. n(n+1)/2 + 1
+1
why the first assumption is needed?

Also null string is by default not a string I guess.
+1
+2
Guess, wikipedia link makes everything clear.
0
Can u plz explain that upto what value will this series go , what will be the last length of substring considered ?
0
upto n simple
0
NULL is a string of length 0..yeah NULL isnt a symbol its just string..
0
why only 3 terms are considered?
0
No, there are n terms, so sum is 1+2+... +n
0
omg. sorry. bhagirathi confused me!
:P
+1
what about empty string , is its length 0 , so will we not consider it ?
+1
empty substring should be considered when it is being generated. when it is being selected from an already given input, then it is trivially illogical to choose the null string.
+1
substring of length 0 is empty string ,rght so it should be included as well I think , it is just asking for substrings which can be formed so why not empty string ?
+7
@radha that option is not in choice. So, they ignored it. Ideally they should have mentioned non-empty but that's how they form questions with choices- if ambiguities are resolved from choices, question is taken as correct.
0
all possible substrings of string  "RAJ"are
"R"
"A"
"J"

"RA"
"AJ"
"RAJ"

????
0
here for RAJ n=3

 No of possible substrings excluding null string = (3*4)/2  =6
–3 votes
answered by Loyal (7.3k points)


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

39,441 questions
46,623 answers
139,378 comments
57,028 users