Count Special Substrings in a DNA Sequence

You are given a DNA sequence string genome, consisting of lowercase Latin letters.

A substring of genome is considered special if it satisfies one of the following conditions:

The length of the substring is exactly 2 and both characters are the same. Example: "aa", "bb"

The length of the substring is greater than 2, the first and last characters are the same, and the substring in between (from index 1 to n-2) contains exactly one distinct character. Example: "xyyx" -> 'x' == 'x' and the middle "yy" has only one distinct character.

Function Signature

def countSpecialSubstrings(genome: str) -> int:

Input

• A single string genome of length n where:

• 1 ≤ n ≤ 3 * 10^5
• genome contains only lowercase letters ('a' to 'z')

Output

• Return the total count of special substrings in the given genome string.