Задача: 1358. Number of Substrings Containing All Three Characters
Сложность: medium

Дана строка s, состоящая только из символов a, b и c.

Верните количество подстрок, содержащих хотя бы одно вхождение всех этих символов a, b и c.

Пример:

Input: s = "abc"
Output: 1

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

1⃣Инициализация указателей и счетчиков:
Создайте три указателя i, j, и count для отслеживания текущего положения в строке и подсчета подстрок. Используйте словарь для подсчета вхождений символов a, b, и c.

2⃣Расширение окна:
Перемещайте правый указатель j по строке и увеличивайте счетчики символов в словаре. Как только все три символа (a, b, и c) присутствуют в текущем окне, начинайте уменьшать левый указатель i.

3⃣Уменьшение окна и подсчет подстрок:
Для каждого сдвига i вправо, проверяйте наличие всех символов в текущем окне. Если все символы присутствуют, добавьте количество подстрок, заканчивающихся в позиции j, к общему счету. Сдвигайте i вправо до тех пор, пока условие выполнения не нарушится.
Верните итоговое количество подстрок.

😎 Решение:

class Solution {
    func numberOfSubstrings(_ s: String) -> Int {
        let chars = Array(s)
        var count = 0
        var i = 0
        var charCount = [Character: Int]()
        
        for j in 0..<chars.count {
            charCount[chars[j], default: 0] += 1
            
            while charCount.keys.contains("a") && charCount.keys.contains("b") && charCount.keys.contains("c") {
                count += chars.count - j
                charCount[chars[i]]! -= 1
                if charCount[chars[i]]! == 0 {
                    charCount.removeValue(forKey: chars[i])
                }
                i += 1
            }
        }
        
        return count
    }
}

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