Sobes.tech
Назад к вопросам
Intern
4

/* дана строка символов. Найти количество пар индексов i и j (i <= j), между которыми нет повторяющихся символов. Для строки "aba" ответ 5: могут быть аски [0, 0] ("a") [0, 1] ("ab") [1, 1] ("b") [1, 2] ("ba") [2, 2] ("a") */

Компании, где спрашивали
Яндекс

Ответ от нейросети

sobes.tech AI

Для решения задачи нужно перебрать все подстроки строки и проверить, что в каждой подстроке нет повторяющихся символов. Чтобы сделать это эффективно, можно использовать скользящее окно с двумя указателями и множество для отслеживания уникальных символов.

Пример на Go:

func countUniqueSubstrings(s string) int {
    n := len(s)
    count := 0
    chars := make(map[byte]bool)
    j := 0

    for i := 0; i < n; i++ {
        for j < n && !chars[s[j]] {
            chars[s[j]] = true
            j++
        }
        count += j - i
        delete(chars, s[i])
    }
    return count
}

// Пример использования:
// s := "aba"
// fmt.Println(countUniqueSubstrings(s)) // Выведет 5

Идея: расширяем правый указатель j, пока символы уникальны, затем сдвигаем левый указатель i, удаляя символы из множества. Количество уникальных подстрок, начинающихся с i, равно j - i.