In the string "abacad", the letter "a" appears 3 times. How many substrings begin with the first "a" and end with any "a"?

There are 3 substrings ("a", "aba", and "abaca"). How many substrings begin with the second "a" and end with any "a"? How about the third?

2 substrings begin with the second "a" ("a", and "aca") and 1 substring begins with the third "a" ("a").

There is a total of 3 + 2 + 1 = 6 substrings that begin and end with "a".

If a character appears i times in the string, there are i * (i + 1) / 2 substrings that begin and end with that character.