Corgis are interesting. They have genes - but in a world of Corgis, the genes are not expressed by the standard 'ATCG' bases, but rather, there are $$$26$$$ bases, each represented by a unique lowercase English letter.
You, a genetic scientist, are here to understand a corgi's genes. Since genetic diversity is viewed to be beneficial to a corgi's health, you are specifically looking for "interesting" sub-genes (substrings) of a corgi's genes that do not contain more than two of any single gene (letter). You additionally want the sub-genes to be "interesting" – in this case, you want palindrome sub-genes (a palindrome is a string which is read the same forwards as it is backwards).
However, the sub-genes' lengths are quite long, and you are lazy. Develop a program that helps you count the number of distinct "interesting" sub-gene ranges that do not contain more than two of the same gene, given the corgi's gene formation.
One line containing $$$n\ (1\leq n\leq 5\cdot 10^4)$$$ continuous lowercase English letters, representing the gene of the corgi.
A single integer, representing the number of non-empty palindromic sub-genes where no more than two of the same gene is present.
ababa
8
In this case, there are $$$8$$$ distinct ranges that satisfy the "palindrome" and "no more than 2 of each letter" requirements: [1,1]; [2,2]; [3,3]; [4,4]; [5,5]; [1,3]; [2,4]; [3,5].
Observe that [1,5]="ababa" is not valid since it contains 3 instances of the letter a.
