Подсчёт подстрок без повторяющихся символов

Условие

Дана строка, состоящая только из строчных латинских букв. Требуется определить количество её подстрок, в которых каждый символ встречается не более одного раза.

Примеры: aba → a, b, ab, ba, a → 5 abc → a, b, c, ab, bc, abc → 6

Ответ

Поддерживайте окно без повторов и последнюю позицию каждой буквы. Для правого конца right существует right - left + 1 подходящих подстрок; суммируйте эти количества.

public long countUniqueSubstrings(String s) {
    int[] last = new int[26];
    java.util.Arrays.fill(last, -1);
    int left = 0;
    long count = 0;
    for (int right = 0; right < s.length(); right++) {
        int c = s.charAt(right) - 'a';
        left = Math.max(left, last[c] + 1);
        count += right - left + 1;
        last[c] = right;
    }
    return count;
}

Вход соответствует условию: только a–z. Время O(n), память O(26). Считаются вхождения подстрок, не разные значения: обе буквы a в aba учитываются отдельно. Результаты — 5 и 6.