LeetCode 1100 - Find K-Length Substrings With No Repeated Characters

Difficulty: 🟡 Medium
Topics: Hash Table, String, Sliding Window

Solution

Problem Understanding

The problem asks us to count how many substrings of length k contain only unique characters.

A substring is a contiguous portion of the string. For every possible substring of length k, we must determine whether all characters inside it are distinct. If they are, we count that substring toward the final answer.

For example, consider:

s = "havefunonleetcode"
k = 5

The substring "havef" contains the characters h, a, v, e, and f, all distinct, so it is valid. The substring "funon" contains two n characters, so it is invalid.

The input consists of:

A string s containing only lowercase English letters
An integer k

The output is a single integer representing the number of valid substrings of length k.

The constraints are important:

1 <= s.length <= 10^4
1 <= k <= 10^4

A string length of 10^4 is large enough that repeatedly checking every substring character by character could become inefficient. This suggests we should look for a linear-time or near-linear-time solution.

There are several important edge cases:

k > len(s), no substring of length k can exist
k == 1, every single character substring is automatically valid
Strings with all repeated characters, such as "aaaaa"
Strings where every character is unique
Windows where duplicates enter and leave as the sliding window moves

The problem guarantees that the string only contains lowercase English letters, which means we can use fixed-size frequency arrays if desired.

Approaches

Brute Force Approach

The brute-force solution examines every substring of length k.

For each starting index:

Extract the substring of size k
Check whether all characters are unique
If unique, increment the answer

To test uniqueness, we can insert characters into a set. If we encounter a character already in the set, the substring is invalid.

This approach is correct because it directly evaluates every possible substring exactly according to the problem definition.

However, it is inefficient. There are roughly n - k + 1 substrings, and checking uniqueness costs O(k) time. Therefore, the total complexity becomes O(n * k).

With n = 10^4, this can become unnecessarily slow.

Optimal Sliding Window Approach

The key observation is that consecutive substrings overlap heavily.

For example:

"havef"
"avefu"

These two substrings share four characters. Instead of rebuilding the character set from scratch for every window, we can reuse information from the previous window.

This naturally leads to a sliding window approach.

We maintain:

A left pointer
A right pointer
A frequency map of characters inside the current window

As the right pointer expands the window:

Add the new character
If duplicates appear, shrink the window from the left until all characters are unique again
Whenever the window size becomes exactly k, count it as valid

Because each character enters and leaves the window at most once, the algorithm runs in linear time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * k)	O(k)	Rechecks every substring independently
Optimal	O(n)	O(1)	Sliding window with character frequency tracking

Algorithm Walkthrough

Optimal Sliding Window Algorithm

Handle the impossible case first.

If k > len(s), return 0 immediately because no substring of length k can exist. 2. Create a frequency map.

We need to track how many times each character appears inside the current window. Since the string contains only lowercase English letters, we can use an array of size 26. 3. Initialize pointers and answer.

Set:

left = 0
answer = 0

The window will expand using the right pointer. 4. Expand the window one character at a time.

For each character at index right:

Add it to the frequency map
Increase its count

Remove duplicates if necessary.

If the current character appears more than once, the window is invalid because it contains duplicates.

While duplicates exist:

Remove s[left] from the frequency map
Move left forward

This restores the invariant that all characters inside the window are unique. 6. Maintain window size.

If the window grows larger than k, shrink it from the left until its size becomes at most k. 7. Count valid windows.

Whenever the window size becomes exactly k, all characters are unique by construction.

Therefore:

Increment the answer

Continue until the entire string has been processed.

Why it works

The algorithm maintains an important invariant:

The current sliding window always contains unique characters.

Whenever a duplicate appears, the left side of the window moves forward until the duplicate is removed. Therefore, if the window size reaches exactly k, we know all k characters are distinct.

Since every valid substring appears exactly once as the sliding window moves, the algorithm counts all valid substrings correctly.

Python Solution

class Solution:
    def numKLenSubstrNoRepeats(self, s: str, k: int) -> int:
        n = len(s)

        if k > n:
            return 0

        frequency = [0] * 26

        left = 0
        answer = 0

        for right in range(n):
            right_index = ord(s[right]) - ord('a')
            frequency[right_index] += 1

            while frequency[right_index] > 1:
                left_index = ord(s[left]) - ord('a')
                frequency[left_index] -= 1
                left += 1

            while right - left + 1 > k:
                left_index = ord(s[left]) - ord('a')
                frequency[left_index] -= 1
                left += 1

            if right - left + 1 == k:
                answer += 1

        return answer

The implementation begins by checking whether k exceeds the string length. If so, the function immediately returns 0.

The frequency array stores how many times each lowercase letter appears inside the current window. Using an array instead of a dictionary is efficient because the alphabet size is fixed at 26.

The right pointer expands the window one character at a time. Every time a character is added, its frequency increases.

If the added character causes a duplicate, the first while loop shrinks the window from the left until the duplicate disappears.

The second while loop ensures the window never exceeds size k.

Finally, whenever the window size equals k, the substring is guaranteed to contain unique characters, so the answer increases.

Go Solution

func numKLenSubstrNoRepeats(s string, k int) int {
	n := len(s)

	if k > n {
		return 0
	}

	frequency := make([]int, 26)

	left := 0
	answer := 0

	for right := 0; right < n; right++ {
		rightIndex := s[right] - 'a'
		frequency[rightIndex]++

		for frequency[rightIndex] > 1 {
			leftIndex := s[left] - 'a'
			frequency[leftIndex]--
			left++
		}

		for right-left+1 > k {
			leftIndex := s[left] - 'a'
			frequency[leftIndex]--
			left++
		}

		if right-left+1 == k {
			answer++
		}
	}

	return answer
}

The Go implementation follows the same logic as the Python version.

The frequency structure is implemented as a fixed-size integer slice of length 26. Since Go strings are byte indexed and the input contains only lowercase English letters, accessing characters with s[i] is safe and efficient.

Go does not require special handling for integer overflow here because all counts remain well within the range of standard integers.

Worked Examples

Example 1

s = "havefunonleetcode"
k = 5

We trace the sliding window:

Step	Window	Unique?	Count
havef	yes	valid	1
avefu	yes	valid	2
vefun	yes	valid	3
efuno	yes	valid	4
funon	no, duplicate n	invalid	4
unonl	no, duplicate n	invalid	4
nonle	no, duplicate n	invalid	4
onlee	no, duplicate e	invalid	4
nleet	no, duplicate e	invalid	4
leetc	no, duplicate e	invalid	4
eetco	no, duplicate e	invalid	4
etcod	yes	valid	5
tcode	yes	valid	6

Final answer:

Example 2

s = "home"
k = 5

Since k > len(s):

5 > 4

No substring of size 5 can exist.

Final answer:

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each character enters and leaves the sliding window at most once
Space	O(1)	Frequency array size is fixed at 26

The algorithm is linear because both pointers only move forward. Even though there are nested while loops, every character is removed from the window at most once.

The space complexity is constant because the frequency array never grows with input size.

Test Cases

solution = Solution()

assert solution.numKLenSubstrNoRepeats("havefunonleetcode", 5) == 6
# Standard example with multiple valid substrings

assert solution.numKLenSubstrNoRepeats("home", 5) == 0
# k larger than string length

assert solution.numKLenSubstrNoRepeats("abcde", 5) == 1
# Entire string is one valid substring

assert solution.numKLenSubstrNoRepeats("aaaaa", 2) == 0
# All repeated characters

assert solution.numKLenSubstrNoRepeats("abcdef", 1) == 6
# Every single character substring is valid

assert solution.numKLenSubstrNoRepeats("abac", 3) == 0
# Every length-3 window contains duplicates

assert solution.numKLenSubstrNoRepeats("abcd", 2) == 3
# Multiple overlapping valid windows

assert solution.numKLenSubstrNoRepeats("aababcabc", 3) == 4
# Sliding window repeatedly removes duplicates

assert solution.numKLenSubstrNoRepeats("", 1) == 0 if False else True
# Empty string excluded by constraints, placeholder edge awareness

Test Case Summary

Test	Why
`"havefunonleetcode", 5`	Verifies standard sliding window behavior
`"home", 5`	Validates impossible case where k is too large
`"abcde", 5`	Tests full-string valid substring
`"aaaaa", 2`	Ensures duplicates are rejected
`"abcdef", 1`	Confirms smallest window size behavior
`"abac", 3`	Tests windows containing unavoidable duplicates
`"abcd", 2`	Verifies overlapping valid substrings
`"aababcabc", 3`	Stress test for repeated duplicate removals

Edge Cases

Case 1: `k` Larger Than the String Length

If k > len(s), no substring of the required size can exist. A naive implementation might still attempt to create windows or access invalid indices.

The solution prevents this by immediately returning 0 before any sliding window logic begins.

Case 2: Repeated Characters Everywhere

Consider:

s = "aaaaaa"
k = 2

Every window contains duplicate characters. Some implementations incorrectly count windows after shrinking only once.

This solution repeatedly shrinks the window until all duplicates are removed, guaranteeing correctness.

Case 3: Window Size Exactly Equal to the Entire String