Задача: 567. Permutation in String
Сложность: medium

Даны две строки s1 и s2. Верните true, если s2 содержит перестановку s1, или false в противном случае.

Другими словами, верните true, если одна из перестановок s1 является подстрокой s2.

Пример:

Input: s1 = "ab", s2 = "eidbaooo"
Output: true
Explanation: s2 contains one permutation of s1 ("ba").

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

1⃣Создать массив для подсчета символов в строке s1. Затем создать аналогичный массив для первых len(s1) символов строки s2.

2⃣Использовать скользящее окно для перемещения по строке s2. Для каждой позиции окна обновлять массив подсчета символов и сравнивать его с массивом для строки s1.

3⃣Если массивы совпадают на любом этапе, вернуть true. Если окно достигает конца строки s2 и совпадений не найдено, вернуть false.

😎 Решение:

class Solution {
    func checkInclusion(_ s1: String, _ s2: String) -> Bool {
        let s1Len = s1.count, s2Len = s2.count
        if s1Len > s2Len { return false }
        
        let s1Arr = Array(s1), s2Arr = Array(s2)
        var s1Count = [Int](repeating: 0, count: 26)
        var s2Count = [Int](repeating: 0, count: 26)
        
        for i in 0..<s1Len {
            s1Count[Int(s1Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
            s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] += 1
        }
        
        for i in 0..<(s2Len - s1Len) {
            if s1Count == s2Count { return true }
            s2Count[Int(s2Arr[i].asciiValue! - Character("a").asciiValue!)] -= 1
            s2Count[Int(s2Arr[i + s1Len].asciiValue! - Character("a").asciiValue!)] += 1
        }
        
        return s1Count == s2Count
    }
}

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