Given a string s and an integer k, return the number of substrings in s 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, it is not possible to find any substring.
Constraints:
1 <= s.length <= 104s consists of lowercase English letters.1 <= k <= 104Problem Overview: Given a string s and an integer k, count how many substrings of length k contain only unique characters. Every character inside the window must appear exactly once.
Approach 1: Brute Force with Set Check (O(n * k) time, O(k) space)
Iterate over every possible substring of length k. For each starting index, extract the substring and insert its characters into a set. If the set size equals k, the substring contains no duplicates. This approach directly checks uniqueness but repeatedly scans overlapping substrings, which makes it inefficient when k is large. Still useful as a baseline implementation and helps validate the sliding window optimization.
Approach 2: Sliding Window + Hash Table (O(n) time, O(min(n, k)) space)
Maintain a window of size k using two pointers. A frequency map (hash table) tracks how many times each character appears in the current window. As you expand the right pointer, increment the character count. When the window exceeds size k, remove the leftmost character and update the map. A valid substring occurs when the window length is k and every character frequency is exactly one.
The key insight: instead of re-checking the entire substring, reuse information from the previous window. Each character is added and removed at most once, giving linear traversal of the string. Hash lookups and updates happen in constant time.
This pattern appears frequently in sliding window problems that track constraints inside a fixed-size substring. The frequency map is typically implemented using a dictionary or array, which is a standard use of a hash table. Since the input is a sequence of characters, the problem also falls under classic string processing techniques.
Recommended for interviews: The sliding window + hash table approach. Interviewers expect you to recognize overlapping substrings and avoid recomputing uniqueness from scratch. Showing the brute force idea first demonstrates understanding of the problem space, but the O(n) sliding window solution shows mastery of common string optimization patterns.
We maintain a sliding window of length k, and use a hash table cnt to count the occurrences of each character in the window.
First, we add the first k characters of the string s to the hash table cnt, and check whether the size of cnt is equal to k. If it is, it means that all characters in the window are different, and the answer ans is incremented by one.
Next, we start to traverse the string s from k. Each time we add s[i] to the hash table cnt, and at the same time subtract s[i-k] from the hash table cnt by one. If cnt[s[i-k]] is equal to 0 after subtraction, we remove s[i-k] from the hash table cnt. If the size of the hash table cnt is equal to k at this time, it means that all characters in the window are different, and the answer ans is incremented by one.
Finally, return the answer ans.
The time complexity is O(n), and the space complexity is O(min(k, |\Sigma|)), where n is the length of the string s; and \Sigma is the character set, in this problem the character set is lowercase English letters, so |\Sigma| = 26.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force with Set | O(n * k) | O(k) | Small inputs or when first reasoning about the problem |
| Sliding Window + Hash Table | O(n) | O(min(n, k)) | General case and optimal interview solution |
Leetcode 1100: Find K Length Substrings With No Repeated Characters • Algorithms Casts • 1,331 views views
Watch 9 more video solutions →Practice Find K-Length Substrings With No Repeated Characters with our built-in code editor and test cases.
Practice on FleetCode