Counting Substrings with Matching Ends

Given a string s, your task is to count the number of contiguous substrings that start and end with the same character. A substring is defined as a contiguous sequence of characters within the string. For a string of length n, note that the total number of substrings is given by \(\frac{n(n+1)}{2}\), but here we only count those substrings whose first and last characters are identical.

Example 1: For s = "abcab", the valid substrings are: "a", "b", "c", "a", "b", "aba", and "bab", which totals 7 substrings.

Example 2: For s = "aaaa", the valid substrings are: "a", "a", "a", "a", "aa", "aa", "aa", "aaa", "aaa", and "aaaa", totaling 10 substrings.

inputFormat

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

outputFormat

Output a single integer representing the number of contiguous substrings of s that start and end with the same character.

abcab

7