Задача: 340. Longest Substring with At Most K Distinct Characters
Сложность: medium

Дана строка s и целое число k. Верните длину самой длинной подстроки s, которая содержит не более k различных символов.

Пример:

Input: n = 27
Output: true
Explanation: 27 = 3^3

👨‍💻 Алгоритм:

1⃣Инициализация
Используйте два указателя (left и right) для отслеживания текущего окна в строке. Создайте словарь для отслеживания количества каждого символа в текущем окне. Инициализируйте переменные для хранения максимальной длины подстроки (max_length).

2⃣Раздвижение окна
Перемещайте правый указатель (right) по строке и обновляйте словарь. Если количество различных символов в словаре превышает k, перемещайте левый указатель (left) вправо, уменьшая счетчик символов, пока количество различных символов снова не станет меньше или равно k.

3⃣Обновление максимальной длины
На каждом шаге проверяйте и обновляйте максимальную длину подстроки, если текущее окно содержит не более k различных символов. В конце верните максимальную длину подстроки.

😎 Решение:

class Solution {
    fun lengthOfLongestSubstringKDistinct(s: String, k: Int): Int {
        var left = 0
        var right = 0
        val charCount = mutableMapOf<Char, Int>()
        var maxLength = 0
        
        while (right < s.length) {
            charCount[s[right]] = charCount.getOrDefault(s[right], 0) + 1
            while (charCount.size > k) {
                charCount[s[left]] = charCount[s[left]]!! - 1
                if (charCount[s[left]] == 0) {
                    charCount.remove(s[left])
                }
                left++
            }
            maxLength = maxOf(maxLength, right - left + 1)
            right++
        }
        
        return maxLength
    }
}

Ставь 👍 и забирай 📚 Базу знаний