Сложность: 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:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if k > 26:
return 0
n = len(s)
answer = 0
for i in range(n - k + 1):
freq = [0] * 26
is_unique = True
for j in range(i, i + k):
freq[ord(s[j]) - ord('a')] += 1
if freq[ord(s[j]) - ord('a')] > 1:
is_unique = False
break
if is_unique:
answer += 1
return answer
Ставь 👍 и забирай 📚 Базу знаний