2
$\begingroup$

string = "abcd" I'm looking for the formula which gives all the possible substrings but the substrings are limited in length.

For example all possible substrings for "abcd" are 4*(4+1)/2 = 10 But here I'm looking for all the possible substrings which have a max length of 2, the result is 7 but what is the formula ?

thanks a lot for your help

EDIT: I'm interested of the number of substring possible, in order, with a max length of 2, for example "abcd" => a, b, c, d, ab, bc, cd => 7 "1111" => 1, 1, 1, 1, 11, 11, 11 => 7

A comment from @lulu that makes my question more clear: I believe the OP is requiring the substring to consist of consecutive elements of the string. Furthermore, judging from the answer to my question about 1111, the OP isn't interested in the string itself...just in its start and end location

$\endgroup$
  • $\begingroup$ sure downvote but tell me why or say it's a duplicate, I haven't found a duplicate of this for now $\endgroup$ – François Richard Sep 24 '18 at 9:46
  • 2
    $\begingroup$ This is not clear. If your string is $1111$, how many substrings are there? $\endgroup$ – lulu Sep 24 '18 at 9:49
  • 1
    $\begingroup$ @N.F.Taussig I believe they are counting them as "a", "b", "c", "d", "ab", "bc", "cd", "abc", "bcd", and "abcd" (that is letters have to remain in order not randomly selected from all letters in the string) $\endgroup$ – lioness99a Sep 24 '18 at 9:50
  • 1
    $\begingroup$ @N.F.Taussig I believe the OP is requiring the substring to consist of consecutive elements of the string. Furthermore, judging from the answer to my question about $1111$, the OP isn't interested in the string itself...just in its start and end locations. $\endgroup$ – lulu Sep 24 '18 at 9:54
  • 1
    $\begingroup$ If the question is just about the number of ways to specify the first and last members of a substring of defined length, I'd say the answer was (clearly) $n+(n-1)=2n-1$ as $n$ elements can be the start of a length $1$ substring and $n-1$ can be the start of a length $2$ substring. But I am not sure I have the question right. $\endgroup$ – lulu Sep 24 '18 at 9:56
5
$\begingroup$

To sum up the discussion in the comments: the reference to substrings is misleading as the OP is not interested in the characters that make up the substring, only in the possible locations of their first and last elements. Thus, the question is asking "given two natural numbers $m≤n$, how many pairs $(i,j)$ are possible with $1≤i<j≤n$ and $j-i≤m$?"

Let $F(n,m)$ denote the desired answer.

Example: for $m=2$, there are $n$ places that might be the first element of a length $1$ substring, and there are $n-1$ that might be the first element of a continuous length $2$ substring. Thus $$F(n,2)=n+(n-1)=2n-1$$

In general, there are $n-(k-1)$ places that might be the start of a continuous length $k$ substring. Thus the answer is $$F(n,m)=n+(n-1)+\cdots + (n-(m-1))=m\times n -\sum_{i=0}^{m-1} i=m\times n-T_{m-1}$$

Where $T_i$ denotes the $i^{th}$ Triangular Number. Thus $$T_i=\frac {i(i+1)}2$$

Examples:

$$F(n,2)=2n-T_1=2n-1$$ $$F(4,4)=4\times 4-T_3=16-6=10$$

$\endgroup$
2
$\begingroup$

For "abc" valid substrings of length $2$ or less are "a", "b", "c", "ab", "bc", so $5$

For "abcd" we have $7$, as noted in your question, for "abcde" we have $9$, and for "abcdef" we have $11$

From this pattern, we can guess that, for a string of length $m$, there will be $2m - 1$ substrings of length $2$ or less

If we want length $3$ or less, then for "abc", we have $6$, "abcd" we have $9$, for "abcde" we have $12$ and for "abcdef" we have $15$

Here we can guess that there will be $3m-3$ substrings of length $3$ or less in a string of length $m$

Similarly, for length $4$ or less, we have $4m-6$ substrings in a string of length $m$

So, we can see the first term is simply $nm$ and we consider the second term of each formula. We note that for a substring of length $1$, this term would be zero, and so we are looking at the sequence $0,1,3,6,\ldots$. We note that a formula for this sequence (found through Wolfram|Alpha) is $$\frac 12(n-1)n$$

Therefore, we propose that, for substrings of length $n$ or less in a string of length $m$, we have $$nm - \frac12(n-1)n$$

We can then check this by counting other strings and substrings

$\endgroup$
  • $\begingroup$ Note: you reversed the OP's notation. In the original problem, $n$ is the length of the entire string and $m$ is the maximum length of the desired substrings, you switched those. But my other objection still stands: it doesn't suffice to point out that the first few examples match a well known sequence, you have to prove that the two sequences coincide. $\endgroup$ – lulu Sep 24 '18 at 10:32
  • $\begingroup$ yes, I'll validate you lulu because you wrote the answer first, I just had more difficulties to read it (I'm bad I know) but you had the same formula $\endgroup$ – François Richard Sep 24 '18 at 10:33
  • 1
    $\begingroup$ thanks a lot for your effort, answer and great explanation $\endgroup$ – François Richard Sep 24 '18 at 10:34
  • $\begingroup$ The OP didn't have a notation in the post, I'd like to hope my answer was still understandable! And @FrançoisRichard you don't have to accept answers because they were first, accept the one that helped you understand (not saying mine did, just a point to note as that then helps other people with the same problem as you) $\endgroup$ – lioness99a Sep 24 '18 at 10:36
  • $\begingroup$ your answer was great, @lulu helped to clarify the problem in the comment ,you both provided great answer $\endgroup$ – François Richard Sep 24 '18 at 10:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.