1.8k 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 | 1.8k views
0

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}$.

edited
+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
0

Why this answer to exactly same question?

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

0

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

1
2