Description
https://leetcode.com/problems/find-k-length-substrings-with-no-repeated-characters/
Given a string s, return the number of substrings of length k with no repeated characters.
Example 1:
Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are : 'havef','avefu','vefun','efuno','etcod','tcode'.
Example 2:
Input: s = "home", k = 5 Output: 0 Explanation: Notice k can be larger than the length of s. In this case is not possible to find any substring.
Note:
1 <= s.length <= 104- All characters of s are lowercase English letters.
1 <= k <= 104
Explanation
Iterate each character and check if there is a string with no repeating character at length of k starting from the character.
Python Solution
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
if k > len(s):
return 0
count = 0
for i in range(len(s) - k + 1):
visited = set()
for j in range(i, i + k):
c = s[j]
if c in visited:
break
else:
visited.add(c)
if len(visited) == k:
count += 1
return count
- Time Complexity: O(N^2).
- Space Complexity: O(N).