0

You have a string of characters {ABCDE}.

You want to know how many substrings of consecutive characters that are three digits long exist.

So you have:

{ABC},{BCD},{CDE}

So my question is: how do I expand this to any arbitrary arguments for the string length and the length of each substring?

O.S.
  • 592
  • 1
    Count the possible starting locations. There are $n - k + 1$ of them. – Qiaochu Yuan Jan 17 '21 at 03:06
  • @QiaochuYuan Thanks so much. I know it's a really simple question but it took me a while to prove it until I realized that the number of possible starting positions is equal to the total amount of positions minus the number of impossible starting positions – O.S. Jan 17 '21 at 03:55
  • 1
    No problem, it can be tricky to make sure you've handled these off-by-one situations properly. Here's a more abstract argument: show by induction that the answer increases by $1$ when $n$ increases by $1$ and decreases by $1$ when $k$ decreases by $1$, so it suffices to check the answer for, say, $n = k = 1$. – Qiaochu Yuan Jan 17 '21 at 03:58

1 Answers1

0

Thanks @QiaochuYuan for giving me the answer. After thinking about it for a bit I've come to the proof:

The number of possible substrings is equal to the number of starting locations:

Possible substrings = Number of starting locations

The number of starting locations is equal to the total number of locations ($n$) minus the number of impossible starting locations.

Number of starting locations = $n$ - Number of impossible starting locations

The number of impossible starting locations is $k-1$. This is because the last possible substring occurs at the $(n-k)$th digit, because $(n-k) + k = n$, and you cannot exceed the value of $n$.

So the total number of possible substrings of length $k$ formed of consecutive characters of a string of length $n$ is:

$n - (k -1) = n - k + 1$

O.S.
  • 592