The Assignment

If we extend the sub-strings $s_1$, $s_2$, and $s_3$ to the end of the string $s$, the score of the sub-string triplet won’t change. So, from now on, we will consider the sub-strings as suffixes for simplicity.

Build the suffix array and corresponding $LCP$ array of the string $s$. The lexicographic order of the suffixes is known now. From now on, the $i^{th}$ suffix means the $i^{th}$ suffix of the suffix array. Let’s say, we have chosen three suffixes $i$, $j$, and $k$ from the suffix array where $i < j < k$. It will be a good sub-string triplet surely. What will be the score of it? Here, we can observe that $p$ is the longest common prefix of the $i^{th}$ and $j^{th}$ suffix, $q$ is the longest common prefix of the $j^{th}$ and $k^{th}$ suffix. And we know from the statement that the score of the sub-string triplet is $p\times q$. Recall that the longest common prefix of any two suffixes is equal to the minimum value of the corresponding range in the $LCP$ array.

If we fix the suffix $j$, we can calculate the summation of $p$ for all possible $i<j$. Similarly, we can calculate the summation of $q$ for all possible $k>j$. Then the summation of the scores of the good sub-string triplets where the suffix $j$ acts as $s_2$ will be $=\sum{p} \times \sum{q}$. So, if we can calculate this thing for all possible $j$, we are good to go.

Let’s say, in the $LCP$ array, the value $LCP_i$ is minimum in $[L, R]$ range $(L \leq i\leq R)$, where $LCP_i$ = longest common prefix of the $i^{th}$ and $(i-1)^{th}$ suffix. It means, if we treat any suffix in $[L-1, i-1]$ range as $s_1$ and treat any suffix in $[i, R]$ range as $s_2$, the value of $p$ will be $LCP_i$ for all of them. So, we can add $LCP_i$ to $[i,R]$ range. If we execute this process for each $LCP_i$, eventually we will get $\sum{p}$ for each $j$. Similarly, we can also calculate $\sum{q}$ for each $j$. As we need to get the values after all the range updates, we can apply prefix sum to perform this in $\mathcal{O}(n)$. We can find the range $[L, R]$ stated above for all the elements in $\mathcal{O}(n)$ by maintaining a monotonous stack. Note that, you need to be careful about overcounting while calculating the $\sum{p}$ and $\sum{q}$.

Time complexity: $\mathcal{O}(n \times log_2(n))$