2955. Number of Same-End Substrings

If there are t occurrences of a character in a substring, there exists t * (t + 1) / 2 Same-End substrings with that character.

Try to calculate the number of occurrences of a character in a substring in O(1) using partial sum.