Самая длинная подстрока с k различными символами

Самая длинная подстрока с k различными символами

Условие задачи

Дана строка из ASCII-символов. Найдите длину самой длинной подстроки, содержащей не более k различных символов.

Пример 1:

1
2
3

Вход: строка="araaci", k=2
Выход: 4
Пояснение: самая длинная подходящая подстрока — "araa".

Пример 2:

1
2
3

Вход: строка="araaci", k=1
Выход: 2
Пояснение: самая длинная подходящая подстрока — "aa".

Пример 3:

1
2
3

Вход: строка="cbbebi", k=3
Выход: 5
Пояснение: самые длинные подходящие подстроки — "cbbeb" и "bbebi".

Решение

Будем хранить в частотной таблице количество каждого символа текущего окна:

  1. Добавляем очередной символ к правой границе окна и увеличиваем его частоту.
  2. Если в таблице стало больше k различных символов, сдвигаем левую границу. Уменьшаем частоту выходящего символа и удаляем его из таблицы, когда частота становится равной нулю.
  3. После сжатия сравниваем длину текущего окна с максимальной найденной длиной.

Код

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

package main

import "fmt"

func longestSubstringWithKDistinct(text string, k int) int {
	if k <= 0 {
		return 0
	}

	frequencies := make(map[byte]int)
	windowStart := 0
	maxLength := 0

	for windowEnd := 0; windowEnd < len(text); windowEnd++ {
		character := text[windowEnd]
		frequencies[character]++

		for len(frequencies) > k {
			leftCharacter := text[windowStart]
			frequencies[leftCharacter]--
			if frequencies[leftCharacter] == 0 {
				delete(frequencies, leftCharacter)
			}
			windowStart++
		}

		windowLength := windowEnd - windowStart + 1
		if windowLength > maxLength {
			maxLength = windowLength
		}
	}

	return maxLength
}

func main() {
	fmt.Println("Длина самой длинной подстроки:", longestSubstringWithKDistinct("araaci", 2))
	fmt.Println("Длина самой длинной подстроки:", longestSubstringWithKDistinct("araaci", 1))
	fmt.Println("Длина самой длинной подстроки:", longestSubstringWithKDistinct("cbbebi", 3))
}

Вывод:

1
2
3

Длина самой длинной подстроки: 4
Длина самой длинной подстроки: 2
Длина самой длинной подстроки: 5

Временная сложность

Каждый символ добавляется в окно и удаляется из него не более одного раза, поэтому временная сложность равна \(O(N)\).

Пространственная сложность

В частотной таблице хранится не более k+1 символов, поэтому пространственная сложность равна \(O(k)\).