1
$\begingroup$

I wanted to compute the total length of the substrings of a string for a coding problem I am attempting.

i.e For $input = abcd$ then then required answer would be $4 + 6 + 6 + 4$ i.e) $ abcd + abc + bcd + ab + bc + cd + a + b + c + d$

The total length of substrings where length of the string is $n$ would be

$\sum_{r=1}^{n/2} r * 2 * nCr $ where n is even and

$\sum_{r=1}^{n/2} r * 2 * nCr $ plus addition term $ n/2 * nCr$ where n is odd

I can brute force this an compute it but that would increase the time complexity of the solution.

Could you please help me convert this summation formula to a single equation that can be computed in constant time.

$\endgroup$
  • $\begingroup$ Noting that $$r{n\choose r}=n{n-1\choose r-1}$$ and the symmetry $${n\choose k}={n\choose n-k}$$ together with the identities $$\sum_{k=0}^n{n\choose k}=2^n$$ trivializes this rather drastically, no? $\endgroup$ – Did May 6 '18 at 12:26
  • 1
    $\begingroup$ For $n=4$, I get $\sum_{r=1}^{n/2}r*2*nCr=1*2*4+2*2*6=32\not=20=4+6+6+4$. So how do the formulas relate to the example? $\endgroup$ – Barry Cipra May 6 '18 at 13:07
  • $\begingroup$ @BarryCipra Yes, you are right. The equation is wrong. Turns out the problems doesn't involve combinations at all. $\endgroup$ – thebenman May 6 '18 at 15:42
1
$\begingroup$

Let $n$ be the length of the string and $k$ be a possible length of a substring, so $1\leq k\leq n$. Now the first $n-k+1$ places of the string could be the start of the substring, because you need at least $k-1$ places for the rest of the substring. So there are exactly $n-k+1$ substrings of length $k$, their combined length being $k(n-k+1)$

So if we sum over all possible substring lengths, we get $$S(n)=\sum_{k=1}^n k(n-k+1)=(n+1)\sum_{k=1}^n k - \sum_{k=1}^n k^2 = \frac{n(n+1)^2}{2}-\frac{n(n+1)(2n+1)}{6}$$

I'm sure you can simplify the right hand side yourself. (We really have $S(4)=20$.) The problem is easier than you anticipated, but I'm afraid you cannot calculate it in "constant time", as $S(n)\in\mathcal{O}(n^3)$, but in a line of code? Sure.

$\endgroup$

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.