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

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