Skip to main content
Talentd

Find K-Length Substrings With No Repeated Characters - Solution & Explanation

MediumPremiumFree on FleetCodeHash TableStringSliding Window11 min readAsked at: Amazon
Practice this problem

Problem Statement

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 <= 104
  • s consists 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.

Code

PythonJavaC++GoTypeScriptPHP

Python

Java

C++

Go

TypeScript

PHP

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force with SetO(n * k)O(k)Small inputs or when first reasoning about the problem
Sliding Window + Hash TableO(n)O(min(n, k))General case and optimal interview solution

Video Solution

Leetcode 1100: Find K Length Substrings With No Repeated Characters • Algorithms Casts • 1,335 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Find K-Length Substrings With No Repeated Characters with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters