in Combinatory retagged by
6,782 views
37 votes
37 votes
How many substrings (of all lengths inclusive) can be formed from a character string of length $n$? Assume all characters to be distinct, prove your answer.
in Combinatory retagged by
6.8k views

3 Comments

Reccurrence relation for this problem is

$a_{n} = a_{n-1} + n$ where $a_i, i >= 1$ is numbers of subtrings till $i_{th}$ position of the string with $a_0 = 1$. It's solution is $1+n(n+1)/2$
5
5
edited by

always remember that substring and subsequence are different things.

11
11

5 Answers

49 votes
49 votes
Best answer

Lets take an example . lets consider the given string is $\text\{GATE\}.$

  • So, set of string of length $1 =\{G,A,T,E\}$ ; cardinality of set $= 4.$
  • Set of strings of length $2 =\{GA,AT,TE\}.$
  • Set of strings of length $3=\{GAT,ATE\}.$
  • Set of strings of length $4 =\{GATE\}.$
  • Set of strings of length $0 =\{\}.$


We cannot have any substring of length $5$ as the given string has only $4$ length.

So total no of substrings possible,

 $=0\;\text{length substring} + 1\;\text{length substrings}+2\;\text{length substrings}+3\;\text{length substrings}+$

      $4\;\text{length substrings}.$

$=\left(1+4+3+2+1\right).$

This means for $1$ length substring to $n$ length substrings, countt will sum of the $n$ natural numbers from $1\;\text{to}\;n .$

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

So total no. of substrings possible $=0\;\text{length strings} + \frac{n(n+1)}{2}= 1+\left[\frac{n(n+1)}{2}\right].$

edited by

4 Comments

Why this answer to exactly same question?

https://gateoverflow.in/2458/gate1994-1-15

0
0

@gmrishi

Read this comment by arjun sir

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
0

@vaibhav singh 3 

if instead of substring subsequence is asked then the answer should be 2^n???

$0$ length subsequence → 1
$1$ length subsequence → $n \choose 1$
$2$ length subsequence → $n \choose 2$
$3$ length subsequence → $n \choose 3$
.
.
.
$n$ length subsequence → $n \choose n$

Adding all we get $2^n$.

Therefore the number of subsequences are $2^n$.

0
0
1 vote
1 vote
0 length- 1(epsilon)

1 length- n(we can chhioose any bit of string)

2lengh-  n-1 (on the rhs we have n-1 options as we cant take the first letter as it will become 1length substrng and lhs is fixed as substrinng is contiguos)

3 length substring- n-2(same way rhs last  place has n-2 options as first 2 places cant take this place)

simiarly n length substring- 1

so 1+2+3+............n +1= n(n+1)/2 +1
1 vote
1 vote

I have different approch .

There are n charaters in string let be 1,2,3…..n
there are (n+1) slots between each string slots are denoted by |
| 1 | 2 | 3 | 4 | ….. | n |
so we need to select any two slot to create substring i.e (n+1)C2
plus add zero string . so answer is
(n+1)C2 + 1
(n+1)*(n)/2 + 1

1 comment

great! this is a new approach here :) thanks for sharing
0
0
0 votes
0 votes

The correct answer is n⨉(n+1)/2 +1 .

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