Задача: 1100. Find K-Length Substrings With No Repeated Characters
Сложность: medium

Дана строка s и целое число k. Верните количество подстрок в s длиной k, которые не содержат повторяющихся символов.

Пример:

Input: s = "havefunonleetcode", k = 5
Output: 6
Explanation: There are 6 substrings they are: 'havef','avefu','vefun','efuno','etcod','tcode'.

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

1⃣Если k > 26, верните 0, так как не может быть строки длиной более 26 символов с уникальными символами. Для остальных случаев, где k <= 26, проверьте каждую подстроку длиной k на наличие повторяющихся символов.

2⃣Итерация по строке s от индекса 0 до n - k (включительно), где n - длина строки s:
Для каждого индекса i:
Инициализируйте флаг isUnique как true и массив частот размером 26 для подсчета частот каждого символа.
Итерируйте следующие k символов и увеличивайте частоту каждого встреченного символа в массиве частот.
Если частота любого символа становится больше 1, установите isUnique в false и прекратите итерацию.
Если после итерации по k символам флаг isUnique все еще равен true, увеличьте счетчик ответов на 1.

3⃣Верните количество подстрок без повторяющихся символов после итерации по всем индексам от 0 до n - k.

😎 Решение:

class Solution {
    function numKLenSubstrNoRepeats($s, $k) {
        if ($k > 26) return 0;
        
        $answer = 0;
        $n = strlen($s);
        
        for ($i = 0; $i <= $n - $k; $i++) {
            $freq = array_fill(0, 26, 0);
            $isUnique = true;
            
            for ($j = $i; $j < $i + $k; $j++) {
                $freq[ord($s[$j]) - ord('a')]++;
                if ($freq[ord($s[$j]) - ord('a')] > 1) {
                    $isUnique = false;
                    break;
                }
            }
            
            if ($isUnique) {
                $answer++;
            }
        }
        
        return $answer;
    }
}

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