Given a string comprised solely of the characters $\text{a, b, c}$ we want to know the number of different $(i, j, k)$ triples such that $0 \leq i,j, k < n \text{ (here n denotes the length of the string)}$ satisfying the following two conditios :$\bullet \text{ }s[i] = a, s[j] =b \text{ and } s[k] = c$$\bullet \text{ } (j + 1)^2 = (i+1)(k + 1) $We consider such two tuples, $(i, j, k)$ and $(x, y, z)$ to be different only of $i \neq x$ or $j \neq y$ or $k \neq z$.Example case and solution :  The string $ccaccbbbaccccca$ with $n = 15$.  There are two triplets that satisfy the given constraints, namely $(2, 5, 11)$ and $(8, 5, 3)$. The second solution shows that $i$ is not necessarily less than $k$.I know this is a programming question, but I'm more inclined to look for a mathematical approach that I currently seem to be missing. Since $n$ could be as large as $5 \cdot 10^5$ brute force is not feasible.I've attempted coming by the solution by noticing that in order for $\sqrt{(i + 1)(k + 1) } = (j +1 ) \in \mathbb{N}$, $k +1$ should be of the form $(i + 1) \cdot \alpha^2$ or of the form $\frac{\alpha^2}{i + 1}$.Hence, we would have to iterate and test in order to find the $\alpha$ values that would satisfy our conditions. Later on, I found out by inspecting the process that the latter form covers all the solutions, multiple times, so I would only need to look for answers by using the second form.This still led to a temporal complexity of $O(\sqrt{n} \cdot \sum_{k=1}^{n}\sqrt{k})$.I've been at this for too many hours and I have no idea how to proceed. How would you solve this?I'm guessing $O(n)$ isn't possible but $O(n \log n)$ should probably do the trick.
Finding triples that satisfy given constraints in $O (n \log n) $ time
algorithms