Задача: 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⃣Отслеживайте максимальную длину допустимой подстроки, обновляя её, когда найдена более длинная подстрока, удовлетворяющая условиям. В конце возвращайте длину самой длинной подстроки.

😎 Решение:

class Solution {
    func longestSubstring(_ s: String, _ k: Int) -> Int {
        let n = s.count
        if n == 0 || k > n {
            return 0
        }
        var countMap = [Int](repeating: 0, count: 26)
        var result = 0
        let sArray = Array(s)
        
        for start in 0..<n {
            countMap = [Int](repeating: 0, count: 26)
            for end in start..<n {
                countMap[Int(sArray[end].asciiValue! - Character("a").asciiValue!)] += 1
                if isValid(countMap, k) {
                    result = max(result, end - start + 1)
                }
            }
        }
        return result
    }
    
    func isValid(_ countMap: [Int], _ k: Int) -> Bool {
        var countLetters = 0, countAtLeastK = 0
        for count in countMap {
            if count > 0 { countLetters += 1 }
            if count >= k { countAtLeastK += 1 }
        }
        return countAtLeastK == countLetters
    }
}

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