Find K-Length Substrings With No Repeated Characters solution and explanation
9 more videos on this problem
Leetcode 1100: Find K Length Substrings With No Repeated CharactersAlgorithms Casts · 18:22 · 1K views
2. Sliding Window | Leetcode | 1100 | Find K-Length Substrings With No Repeated CharactersImran Sarwar · 16:56 · 832 views
Leetcode 1100 - Find K-Length Substrings With No Repeated Characters - Amazon Java Coding InterviewCode With Ben · 13:08 · 441 views
1100. Find K-Length Substrings With No Repeated Characters (Leetcode Medium)Programming Live with Larry · 4:20 · 354 views
米开： LeetCode 1100. Find K-Length Substrings With No Repeated CharactersM.C米开朗基罗 · 6:13 · 291 views
1100. Find K-Length Substrings With No Repeated Characters - Week 2/5 Leetcode March ChallengeProgramming Live with Larry · 5:00 · 237 views
MICROSOFT Coding Question - Find K-Length Substrings With No Repeated Characters | LeetCodeJeanTheCoder · 11:03 · 142 views
#1100 Find K Length Substrings With No Repeated Characters | GFG | LEETCODE | C++ | SDE SHEETYash Chaudhary · 13:56 · 118 views
Find K-Length Substrings With No Repeated CharactersOwen Wu · 2:00 · 33 views
[Daily Leetcode Problem] Leetcode 1100: Find K-Length Substrings With No Repeated CharactersDev Lives Matter · 8:56 · 21 views
The problem
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 <= 104sconsists of lowercase English letters.1 <= k <= 104
Approach overview
Problem 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.
Solution
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.
class Solution:
def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
cnt = Counter(s[:k])
ans = int(len(cnt) == k)
for i in range(k, len(s)):
cnt[s[i]] += 1
cnt[s[i - k]] -= 1
if cnt[s[i - k]] == 0:
cnt.pop(s[i - k])
ans += int(len(cnt) == k)
return ansclass Solution {
public int numKLenSubstrNoRepeats(String s, int k) {
int n = s.length();
if (n < k) {
return 0;
}
Map<Character, Integer> cnt = new HashMap<>(k);
for (int i = 0; i < k; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
}
int ans = cnt.size() == k ? 1 : 0;
for (int i = k; i < n; ++i) {
cnt.merge(s.charAt(i), 1, Integer::sum);
if (cnt.merge(s.charAt(i - k), -1, Integer::sum) == 0) {
cnt.remove(s.charAt(i - k));
}
ans += cnt.size() == k ? 1 : 0;
}
return ans;
}
}class Solution {
public:
int numKLenSubstrNoRepeats(string s, int k) {
int n = s.size();
if (n < k) {
return 0;
}
unordered_map<char, int> cnt;
for (int i = 0; i < k; ++i) {
++cnt[s[i]];
}
int ans = cnt.size() == k;
for (int i = k; i < n; ++i) {
++cnt[s[i]];
if (--cnt[s[i - k]] == 0) {
cnt.erase(s[i - k]);
}
ans += cnt.size() == k;
}
return ans;
}
};function numKLenSubstrNoRepeats(s: string, k: number): number {
const n = s.length;
if (n < k) {
return 0;
}
const cnt: Map<string, number> = new Map();
for (let i = 0; i < k; ++i) {
cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
}
let ans = cnt.size === k ? 1 : 0;
for (let i = k; i < n; ++i) {
cnt.set(s[i], (cnt.get(s[i]) ?? 0) + 1);
cnt.set(s[i - k], (cnt.get(s[i - k]) ?? 0) - 1);
if (cnt.get(s[i - k]) === 0) {
cnt.delete(s[i - k]);
}
ans += cnt.size === k ? 1 : 0;
}
return ans;
}func numKLenSubstrNoRepeats(s string, k int) (ans int) {
n := len(s)
if n < k {
return
}
cnt := map[byte]int{}
for i := 0; i < k; i++ {
cnt[s[i]]++
}
if len(cnt) == k {
ans++
}
for i := k; i < n; i++ {
cnt[s[i]]++
cnt[s[i-k]]--
if cnt[s[i-k]] == 0 {
delete(cnt, s[i-k])
}
if len(cnt) == k {
ans++
}
}
return
}class Solution {
/**
* @param String $s
* @param Integer $k
* @return Integer
*/
function numKLenSubstrNoRepeats($s, $k) {
$n = strlen($s);
if ($n < $k) {
return 0;
}
$cnt = [];
for ($i = 0; $i < $k; ++$i) {
if (!isset($cnt[$s[$i]])) {
$cnt[$s[$i]] = 1;
} else {
$cnt[$s[$i]]++;
}
}
$ans = count($cnt) == $k ? 1 : 0;
for ($i = $k; $i < $n; ++$i) {
if (!isset($cnt[$s[$i]])) {
$cnt[$s[$i]] = 1;
} else {
$cnt[$s[$i]]++;
}
if ($cnt[$s[$i - $k]] - 1 == 0) {
unset($cnt[$s[$i - $k]]);
} else {
$cnt[$s[$i - $k]]--;
}
$ans += count($cnt) == $k ? 1 : 0;
}
return $ans;
}
}Complexity analysis
| 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 |
Frequently asked questions
Is Find K-Length Substrings With No Repeated Characters easy or hard?
The problem is generally classified as Medium because it requires recognizing the sliding window optimization. The brute force idea is simple, but implementing an efficient O(n) solution with proper window updates and frequency tracking requires familiarity with string window patterns.
Find K-Length Substrings With No Repeated Characters Python/Java solution
Most implementations use the same sliding window logic across languages. Python typically uses a dictionary or Counter, while Java uses a HashMap or an int array for character counts. The algorithm iterates once through the string and maintains counts as the window moves.
How to solve Find K-Length Substrings With No Repeated Characters in O(n)?
Use a fixed-size sliding window of length k and maintain a hash map of character frequencies. Expand the window by adding the right pointer and shrink it when the size exceeds k by removing the left pointer character. When the window size equals k and all frequencies are 1, you found a valid substring. This ensures each character is processed only once.
What is the best approach for Find K-Length Substrings With No Repeated Characters?
The most efficient approach uses a sliding window with a hash table (frequency map). Move a window of length k across the string while tracking character counts. When the window size equals k and all characters are unique, increment the result. This runs in O(n) time and avoids recomputing uniqueness for every substring.
Is Find K-Length Substrings With No Repeated Characters asked at Google/Amazon/Meta?
Substring uniqueness and sliding window problems appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as longest substring without repeating characters or fixed-length substring constraints are common patterns used to evaluate string manipulation and window techniques.
What data structure is used in Find K-Length Substrings With No Repeated Characters?
A hash table (dictionary or map) stores the frequency of characters inside the current sliding window. This allows constant-time updates and checks when characters enter or leave the window. Some implementations also use a fixed-size array for ASCII characters.
What is the time complexity of Find K-Length Substrings With No Repeated Characters?
The optimal sliding window solution runs in O(n) time where n is the length of the string. Each character enters and leaves the window at most once. Space complexity is O(min(n, k)) for storing character frequencies in the hash map.