+12 votes
1.6k 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
edited | 1.6k views
0

## 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
+4
Yes. And 2^n if we could have changed the order of characters.
+8
^^ 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 ?
+8
@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
0
here for RAJ n=3

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

Why this answer to exactly same question?

https://gateoverflow.in/87874/gate1989-4-i

–3 votes
answered by Loyal (7.8k points)

+12 votes
2 answers
1
+27 votes
7 answers
2
+16 votes
3 answers
3
+19 votes
4 answers
4
+15 votes
5 answers
5
+15 votes
3 answers
6
+15 votes
3 answers
7