Задача: 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 (strlen($s) == 0 || $k > strlen($s)) {
        return 0;
    }
    $result = 0;

    for ($start = 0; $start < strlen($s); $start++) {
        $countMap = array_fill(0, 26, 0);
        for ($end = $start; $end < strlen($s); $end++) {
            $countMap[ord($s[$end]) - ord('a')]++;
            if (isValid($countMap, $k)) {
                $result = max($result, $end - $start + 1);
            }
        }
    }
    return $result;
}

function isValid($countMap, $k) {
    $countLetters = 0;
    $countAtLeastK = 0;
    foreach ($countMap as $count) {
        if ($count > 0) $countLetters++;
        if ($count >= $k) $countAtLeastK++;
    }
    return $countLetters == $countAtLeastK;
}

echo longestSubstring("aaabb", 3); // Output: 3
echo "\n";
echo longestSubstring("ababbc", 2); // Output: 5

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