Задача: 76. Minimum Window Substring
Сложность: hard

Даны две строки s и t длиной m и n соответственно. Верните наименьшую подстроку строки s так, чтобы каждый символ из строки t (включая дубликаты) входил в эту подстроку. Если такой подстроки не существует, верните пустую строку "".

Тестовые примеры будут сформированы таким образом, что ответ будет уникальным.

Пример:

Input: s = "ADOBECODEBANC", t = "ABC"
Output: "BANC"
Explanation: The minimum window substring "BANC" includes 'A', 'B', and 'C' from string t.

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

1⃣Мы начинаем с двух указателей, left и right, которые изначально указывают на первый элемент строки S.

2⃣Мы используем указатель right для расширения окна до тех пор, пока не получим желаемое окно, т.е. окно, которое содержит все символы из T.

3⃣Как только у нас есть окно со всеми символами, мы можем передвигать указатель left вперёд по одному. Если окно по-прежнему желаемое, мы продолжаем обновлять размер минимального окна. Если окно больше не желаемое, мы повторяем шаг 2 и далее.

😎 Решение:

function minWindow($s, $t) {
    if (strlen($s) === 0 || strlen($t) === 0) {
        return "";
    }
    
    $dictT = [];
    for ($i = 0; $i < strlen($t); $i++) {
        $char = $t[$i];
        if (!array_key_exists($char, $dictT)) {
            $dictT[$char] = 0;
        }
        $dictT[$char]++;
    }
    
    $required = count($dictT);
    $l = 0;
    $r = 0;
    $formed = 0;
    $windowCounts = [];
    $ans = [-1, 0, 0];
    
    while ($r < strlen($s)) {
        $c = $s[$r];
        if (!array_key_exists($c, $windowCounts)) {
            $windowCounts[$c] = 0;
        }
        $windowCounts[$c]++;
        
        if (array_key_exists($c, $dictT) && $windowCounts[$c] === $dictT[$c]) {
            $formed++;
        }
        
        while ($l <= $r && $formed === $required) {
            $c = $s[$l];
            if ($ans[0] === -1 || $r - $l + 1 < $ans[0]) {
                $ans = [$r - $l + 1, $l, $r];
            }
            
            $windowCounts[$c]--;
            if (array_key_exists($c, $dictT) && $windowCounts[$c] < $dictT[$c]) {
                $formed--;
            }
            $l++;
        }
        $r++;
    }
    
    return $ans[0] === -1 ? "" : substr($s, $ans[1], $ans[2] - $ans[1] + 1);
}

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