The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+14 votes
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}$
asked in Combinatory by Veteran (52k points)
edited by | 1.8k views

2 Answers

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

Correct Answer: D

answered by Boss (14.4k points)
edited by
+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
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

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

–3 votes
answered by Loyal (6.9k points)
Answer:

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
49,541 questions
54,071 answers
187,187 comments
70,978 users