Задача: 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.

😎 Решение:

function checkInclusion($s1, $s2) {
    $s1Len = strlen($s1);
    $s2Len = strlen($s2);
    if ($s1Len > $s2Len) return false;

    $s1Count = array_fill(0, 26, 0);
    $s2Count = array_fill(0, 26, 0);

    for ($i = 0; $i < $s1Len; $i++) {
        $s1Count[ord($s1[$i]) - ord('a')]++;
        $s2Count[ord($s2[$i]) - ord('a')]++;
    }

    for ($i = 0; $i < $s2Len - $s1Len; $i++) {
        if ($s1Count == $s2Count) return true;
        $s2Count[ord($s2[$i]) - ord('a')]--;
        $s2Count[ord($s2[$i + $s1Len]) - ord('a')]++;
    }

    return $s1Count == $s2Count;
}

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