567. Permutation in String

Задача

Даны строки s1 и s2. Верните true, если какая-либо перестановка s1 является подстрокой s2.

Примеры

Пример 1

Input: s1 = "ab", s2 = "eidbaooo"
Output: true

Пояснение

s2 содержит перестановку s1 (“ba”).

Пример 2

Input: s1 = "ab", s2 = "eidboaoo"
Output: false

Решение

Решение

/**
 * Сложность по времени: O(N)
 *   Где N — длина строки s2 (длинной строки).
 *   1. Первый цикл проходит M раз (длина s1).
 *   2. Второй цикл (while) проходит (N - M) раз.
 *   Внутри каждого шага while вызывается isZeroes(). Хотя это итерация по массиву,
 *   его размер фиксирован (26), поэтому для Big O это константная операция O(1).
 *   Итоговая сложность: O(M + (N-M) * 26) -> O(N).
 *
 * Сложность по памяти: O(1)
 *   Мы используем массив balance фиксированного размера 26.
 *   Этот размер не зависит от длины входных строк.
 */
var checkInclusion = function (s1, s2) {
    if (s1.length > s2.length) return false;
 
    const A_CODE = 'a'.charCodeAt(0);
    // Используем один массив вместо двух: s1 будет "+", s2 будет "-"
    const balance = new Array(26).fill(0);
 
    const getCode = (letter) => letter.charCodeAt(0) - A_CODE;
    // Проход по 26 элементам — это O(1), так как 26 — константа
    const isZeroes = () => balance.every((value) => value === 0);
 
    // Инициализация окна
    for (let i = 0; i < s1.length; i++) {
        balance[getCode(s1[i])]++;
        balance[getCode(s2[i])]--;
    }
 
    if (isZeroes()) return true;
 
    let right = s1.length;
 
    // Скольжение окна
    while (right < s2.length) {
        // Добавляем новый символ справа (уменьшаем баланс, так как это часть s2)
        const addedLetter = s2[right];
        balance[getCode(addedLetter)]--;
 
        // Удаляем старый символ слева (восстанавливаем баланс, отменяя предыдущий минус)
        const removedLetter = s2[right - s1.length];
        balance[getCode(removedLetter)]++;
 
        if (isZeroes()) return true;
        right++;
    }
 
    return false;
};