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.
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.