Given a string
s, return the number of substrings of length
k with no repeated characters.
Input: s = "havefunonleetcode", k = 5 Output: 6 Explanation: There are 6 substrings they are : 'havef','avefu','vefun','efuno','etcod','tcode'.
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.
1 <= s.length <= 104
- All characters of s are lowercase English letters.
1 <= k <= 104
Iterate each character and check if there is a string with no repeating character at length of k starting from the character.
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).