Задача: 395. Longest Substring with At Least K Repeating Characters
Сложность: medium

Дана строка s и целое число k, верните длину самой длинной подстроки строки s, такая что частота каждого символа в этой подстроке больше или равна k.
Если такой подстроки не существует, верните 0.

Пример:

Input: s = "aaabb", k = 3
Output: 3
Explanation: The longest substring is "aaa", as 'a' is repeated 3 times.

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

1⃣Генерируйте подстроки из строки s, начиная с индекса start и заканчивая индексом end. Используйте массив countMap для хранения частоты каждого символа в подстроке.

2⃣Метод isValid использует countMap для проверки, что каждый символ в подстроке встречается как минимум k раз. Если условие выполняется, текущая подстрока считается допустимой.

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

😎 Решение:

function longestSubstring(s, k) {
    if (s.length === 0 || k > s.length) {
        return 0;
    }
    let result = 0;

    for (let start = 0; start < s.length; start++) {
        let countMap = new Array(26).fill(0);
        for (let end = start; end < s.length; end++) {
            countMap[s.charCodeAt(end) - 97]++;
            if (isValid(countMap, k)) {
                result = Math.max(result, end - start + 1);
            }
        }
    }
    return result;
}

function isValid(countMap, k) {
    let countLetters = 0, countAtLeastK = 0;
    for (let count of countMap) {
        if (count > 0) countLetters++;
        if (count >= k) countAtLeastK++;
    }
    return countLetters === countAtLeastK;
}

console.log(longestSubstring("aaabb", 3)); // Output: 3
console.log(longestSubstring("ababbc", 2)); // Output: 5

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