Решение задачи
Алгоритм решения задачи:
Подумайте о строке «XAXAXXAX» и сосредоточьтесь на том, чтобы сделать второй «A» уникальным символом.
Мы можем взять «XA(XAXX)AX», а между «()» будет наша подстрока.
Здесь мы видим, чтобы вторая буква «А» считалась уникальным символом, нам нужно:
вставьте "(" где-то между первым и вторым A
вставьте ")" где-то между второй и третьей А
Для шага 1 у нас есть "A(XA" и "AX(A", 2 возможности).
Для шага 2 у нас есть «A)XXA», «AX)XA» и «AXX)A», 3 возможности.
Таким образом, всего есть 2 * 3 = 6 способов сделать второй A уникальным символом в подстроке.
Другими словами, есть только 6 подстрок, в которых эта A дает 1 балл как уникальная строка.
Вместо того, чтобы считать все уникальные символы и бороться со всеми возможными подстроками, мы можем посчитать для каждого символа в S, сколько способов найти уникальный символ.
Считаем и суммируем, и это будет ответ.
Объяснение
- index[26][2] записывает индекс двух последних вхождений для каждого верхнего символа.
- Инициализировать все значения в индексе до -1.
- Зацикливаясь на строке S, для каждого символа c обновите индекс двух последних вхождений до index[c].
- Считать, когда петля. Например, если «А» встречается дважды в индексах 3, 6, 9 по отдельности, нам нужно посчитать:
Для первого «А»: (6-3) * (3-(-1))"
Для второго «А»: (9-6) * (6-3)"
Для третьего «А»: (N-9)*(9-6)"
Сложность
Один проход, временная сложность O(N).
Пространственная сложность O(1).
