Количество пар индексов (i, j), таких, что строка после удаления i-го символа равна строке после удаления j-го символа

Для заданной строки str из N символов задача состоит в том, чтобы подсчитать количество допустимых неупорядоченных пар (i, j) , таких что строка после удаления i ^-го символа равна строке после удаления j ^-го символа.

Примеры:

Input: str = “aabb”
Output: 2
Explanation: The string after deletion of 1st element is “abb” and the string after deletion of  2nd element is “abb”. Similarly, the string after deletion of 3rd element is “aab” and the string after deletion of  4th element is “aab”. Hence, the number of valid pairs of (i, j) are 2, i.e, (1, 2) and (3, 4).

Input: str = “aaaaaa”
Output: 15

Подход: Данная проблема может быть решена с использованием следующих наблюдений:

• If S_i = S_j, then S_i = S_i+1 = S_i+2 … = S_j must hold true.
• Also if S_i = S_j, then str[i] = str[i+1] = str[i+2] … = str[j] must hold true as well.

Поэтому, используя приведенные выше наблюдения, можно использовать метод двух указателей для вычисления интервалов (l, r) в строке str таких, что str[l] = str[l+1] … = str[r] , и для для каждого допустимого (l, r) число допустимых пар будет равно ^{r – l} C ₂ .

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)