Секретный код

Заметим, что в результате обмена двух равных букв, строка не меняется. Если же мы меняем две разные буквы, то мы получаем строки, которые отличаются от исходной в фиксированных двух позициях, причем при любом таком обмене мы получим попарно разные строки, так как у нас поменяется разное подмножество позиций исходной строки (иначе это был один и тот же обмен). Значит ответ равен числу пар позиций, на которых находятся разные символы, плюс, возможно, один, если у нас есть пара одинаковых символов(только, так мы можем получить исходную строку). И то, и другое, легко считается за $$$O(|s|)$$$.