2.1k 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}$

edited | 2.1k views
0
+1
let's take an example:

s = ABC

length 0 = 1

lenght 1 = {A , B , C} = 3

length 2 = {AB , BC } = 2

length 3 = {ABC} = 1

total string = length 0 + length 1 + length 2 + length  3 = 1 + 3 + 2 + 1 = 7

option D is the correct answer
0
For length 2,why have u not considered AC?
+2
@anji

AC is not  Substring of ABC   because it is separated by B , Substring is that in which we add another substring , in either left are Right side of Substring to get actual Substring.
0
+3

Substring is defined as "Zero or more Consecutive symbols taken"

What you must be confusing it with is "Subsequence" which is defined as "Zero or more Symbols left out (Consecutive or Not)"

Subword is defined as "One or more Consecutive symbols taken" (Subword is same as substring except for Zero length string)

• Number of substrings of length $n$ is $1$.
• Number of substrings of length $(n-1)$ is $2$.
• Number of substrings of length $(n-2)$ is $3$.

So, total number of substrings $=\frac{n(n+1)}{2}$.

by Boss (14.4k points)
edited
+4
Yes. And 2^n if we could have changed the order of characters.
+9
^^ 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 ?
+2
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 ?
+9
@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
0

Why this answer to exactly same question?

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

+4

Substring$:-$ The substring is a contiguous sequence of characters within a string$.$

$"RAJ"$

$0$ length substring $= \{\}$ $\Rightarrow 1$ substring possible.

$1$ length substring$=\{R,A,J\}\Rightarrow 3$ substrings possible.

$2$ length substring$=\{RA,AJ\}\Rightarrow 2$ substrings possible.

$3$ length substring$=\{RAJ\}\Rightarrow 1$ substring possible.

In general

Number of substrings $=1 + 2 + 3 + ...............+ n + 1$(for empty string)$=\frac{n(n+1)}{2} + 1$

Subsequence$:-$The subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.

$\Rightarrow$All possible substrings and all non-contiguous characters.

$"RAJ"$

subsequences$=\{\epsilon,R,RA,RJ,A,AJ,J,RAJ\}$

Number of subsequences$=2^{n}$

The length of substrings are n or n-1 or n-2 or....or 2 or 1 or 0

let the string is abcd...xyz

no.of substrings of length 'n' = 1           ------  abcd....xyz

no.of substrings of length 'n-1' = 2       ------  abcd....xy , bcd....xyz

no.of substrings of length 'n-2' = 3       ------  abcd....x , bcd....xy , cdef.....xyz

.......

no.of substrings of length '2' = n-1      -----  ab,bc,cd,....vx,xy,yz

no.of substrings of length '1' = n         ------  a,b,c,d,....x,y,z

no.of substrings of length '0' = 1 ----> only empty string is possible

total substrings = 1+2+3+...+(n-1) + n + 1

= [ 1+2+3+...+(n-1) + n ] + 1

= $\frac{n(n+1)}{2}$ + 1

=  ∑n + 1

NOTE :-

Trivial substrings :- empty string ( which is length = 0 ) and the original string ( which is length = n ) are trivial strings.

∴ No.of Trivial substrings are 2 for any non-empty string

Non- Trivial substrings :-  which are not Trivial substrings are called as Non- Trivial substrings.

∴ No.of Non-Trivial substrings are ∑n - 1

Proper Substrings :- the substring which length is less than actual string

∴ No.of Non-Trivial substrings are ∑n

Non-empty Substrings :- the substring which length is grater than 0

∴ No.of Non-Empty substrings are ∑n

by Veteran (65.5k points)
0
This formula works only, when all the alphabets in the given strings are distinct !
by Loyal (7.3k points)