The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+12 votes

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.8k points)
edited by | 1.6k 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.4k points)
edited by
Yes. And 2^n if we could have changed the order of characters.
^^ 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
why the first assumption is needed?

Also null string is by default not a string I guess.
Guess, wikipedia link makes everything clear.
Can u plz explain that upto what value will this series go , what will be the last length of substring considered ?
upto n simple
NULL is a string of length 0..yeah NULL isnt a symbol its just string..
why only 3 terms are considered?
No, there are n terms, so sum is 1+2+... +n
omg. sorry. bhagirathi confused me!
what about empty string , is its length 0 , so will we not consider it ?
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.
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 ?
@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.
all possible substrings of string  "RAJ"are


here for RAJ n=3

 No of possible substrings excluding null string = (3*4)/2  =6
and if subsequence is asked???2^n??

Why this answer to exactly same question?

–3 votes
answered by Loyal (7.8k points)

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

46,648 questions
51,134 answers
66,552 users