Kozak Vus and Strings#10252
Kozak Vus recently encountered the following problem:
Given a string , determine the number of substrings that meet the following criteria:
The substring must contain at least characters.
All characters in the substring are identical except for one.
For instance, the substrings aab and cccdc meet these criteria, whereas ab, ccc, and aabbaa do not.
A string is considered a substring of string if can be derived by removing zero or more characters from the beginning and zero or more characters from the end of .
Assist Kozak Vus in solving this problem.
The first line contains the string (1 \le |s| \le 2 \cdot 10^5), composed of lowercase Latin letters.
Output a single integer — the number of substrings that satisfy the specified conditions.
Example 1
Example 2
Example 3
Example 4
A solution that works correctly for |s| \le 100 will earn at least points.
A solution that works correctly for |s| \le 5000 will earn at least points.