I think the complexity is n2logn . I want to optimise the solution to nlogn or n.
Your complexity isn’t O(n^2logn) but O(n^3). You can solve the problem in O(n^2) by doing this -
Count the number of bad triplets, i.e i, j, k such that s[i] != s[j] != s[k] and j - i = k - j. This can be done by iterating over j, and iterating over i, k at the same time (since they are equidistant to j). Now subtract this from r * g * b (which is number of ways of choosing three different values). This is the answer. My submission - Submission #11811391 - AtCoder Beginner Contest 162