Question

How many substrings (of all lengths inclusive) can be formed from a character string of length 8? (Assume all characters to be distinct)

(a) 14

(b) 21

(c) 54

(d) 37

This question was posed to me by my college director while I was bunking the class.

My query is from Counting in division Counting of Discrete Mathematics

Answer 1

Correct option is (d) 37

The explanation: Let’s consider the given string is CLEAN, so set of string of length 1 = {C,L,E,A,N} ; cardinality of set = 5 set of string of length 2 = {CL,EE,EA,NN}, set of string of length 3 = {CLE,LEE,EAN}, set of strings of length 4 = {CLEN,LEAN}, set of strings of length 5 = {CLEAN} and set of string of length 0 = {} and we cannot have any substring of length 6 as given string has only 5 length. So total no of substrings are possible = 0 length substring + 1 length substring + 2 length substrings +3 length substrings + 4 length substrings + 5 length substrings = 1 + 5 + 4 + 3 + 2 + 1 = 16 means for 1 length string to n length substrings it will sum of the n natural no from 1 to n.

so 1+2+3+…+n = \(\frac{n(n+1)}{2}\) so total no substrings possible = 0 length strings + \(\frac{n(n+1)}{2}\) = 1+ \([\frac{n(n+1)}{2}]\) so total no of substrings possible in n length string (All length inclusive )= 1 + \([\frac{n(n+1)}{2}] = \frac{8(8+1)}{2}\) = 37.