Count Substrings with Same Start and End Characters

You are given a string s. Your task is to count the number of substrings that start and end with the same character. Note that every single character is considered as a valid substring, and substrings of length greater than 1 must have the same first and last characters.

For instance, given the string ababa, the valid substrings are:

• Single characters: a, b, a, b, a
• Substrings: aba, bab, aba, ababa

The total count is 9.

The input string may contain only lowercase letters and can be empty.

inputFormat

The input is read from standard input (stdin) and consists of a single line containing the string s. The string can be empty.

outputFormat

Output the number of substrings of s that start and end with the same character to standard output (stdout).

ababa

9