2
$\begingroup$

Simple counting problem but can't wrap my head around it

ABCD -- Substrings of length 2 : AB, BC, CD. Similarly ABCDE and length 3 -- ABC, BCD, CDE

I see m choose n won't work -- we'll get all subsequences too

2 Answers 2

4

Consider how many of the characters in the string are valid "starting characters" for the substrings you desire. For instance, in "ABCD," only "A", "B", and "C" are valid starting characters for substrings of length 2.

In general, in a string of length $n$, if you want a substring of length $m$, you can only choose the first $n - m + 1$ characters as starting characters.

-1

It's the permutation topic.

1) length of main string : n

2) Select "k" number of charactered in ordered so,

Number of k-substring =

( (n!)/(n-k)! ) = (n-k+1)
number of k-substrings in given string of length n.