The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 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 (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
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?


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


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



Number of subsequences$=2^{n}$

–3 votes
answered by Loyal (6.9k 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
49,541 questions
54,071 answers
70,978 users