find-k-length-substrings-with-no-repeated-characters

< Previous 　　　　　　　　　　　　　　　　 Next >

1100. Find K-Length Substrings With No Repeated Characters (Medium)

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. 1 <= S.length <= 10^4
2. All characters of S are lowercase English letters.
3. 1 <= K <= 10^4

Related Topics

[Hash Table] [String] [Sliding Window]

Hints

Hint 1

How to check efficiently each K-length substring?

Hint 2

First store the first leftmost K-length substring in a hashTable or array of frequencies.

Hint 3

Then iterate through the rest of characters and erase the first element and add the next element from the right. If in the hashTable we have K different character we add 1 to the counter. After that return as answer the counter.