Count Substrings with Matching Ends

Given a non-empty string S consisting of lowercase English letters, your task is to compute the number of non-empty substrings (i.e. contiguous subsequences) whose first and last characters are the same.

For a character that appears f times in the string, the number of substrings starting and ending with that character is given by the formula: \(\frac{f(f+1)}{2}\). The overall answer is the sum of these values for all characters that appear in the string.

Example: For S = "abcab", the answer is 7 because:

• The character 'a' appears 2 times and contributes \(2\times3/2 = 3\) substrings.
• The character 'b' appears 2 times and contributes 3 substrings.
• The character 'c' appears 1 time and contributes 1 substring.

Total = 3+3+1 = 7.

inputFormat

The input consists of a single line containing the string S.

Constraints: S contains only lowercase English letters and has at least 1 character.

outputFormat

Output a single integer representing the total count of substrings whose first and last characters are the same.

abcab

7