We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Find K-Length Substrings With No Repeated Characters

Number: 1084

Difficulty: Medium

Paid? Yes

Companies: Amazon

Problem Description

Given a string s and an integer k, return the number of substrings in s of length k that contain no repeated characters. If k is greater than the length of s, there are no possible substrings, so return 0.

Key Insights

  • Use a sliding window of fixed size k.
  • Track character counts within the current window using a hash table (or frequency array).
  • When a duplicate is found in the window, slide the window from the left to remove duplicates.
  • Count a valid window when its size equals k and all characters are unique.
  • Optimize by adjusting the window immediately after counting a valid substring.

Space and Time Complexity

Time Complexity: O(n) where n is the length of s, as each character is visited at most twice. Space Complexity: O(1) since the frequency tracking is over a fixed set (26 lowercase letters).

Solution

We use a sliding window approach with two pointers: left and right. A hash table (or frequency array) tracks the occurrences of characters in the window. As we move the right pointer, we update the frequency and check for duplicates. If a duplicate is encountered, we increment the left pointer until the duplicate is removed. Once the window size exactly equals k, we have a valid substring, so we increment our count and then slide the window forward. This ensures that every possible k-length substring is examined once.

Code Solutions

def numKLenSubstrNoRepeats(s: str, k: int) -> int:
    # If k is larger than the string length, no valid substring exists.
    if k > len(s):
        return 0
    
    count = 0
    left = 0
    # Dictionary to store the frequency of characters in the current window.
    char_count = {}
    
    # Iterate over the string using right pointer.
    for right in range(len(s)):
        # Update frequency count for the current character.
        char_count[s[right]] = char_count.get(s[right], 0) + 1
        
        # If current character frequency > 1, slide window from the left to remove duplicates.
        while char_count[s[right]] > 1:
            char_count[s[left]] -= 1
            left += 1
        
        # When window size equals k, we have a valid substring.
        if right - left + 1 == k:
            count += 1
            # Slide the window by removing the leftmost character.
            char_count[s[left]] -= 1
            left += 1
    return count

# Example usage:
# print(numKLenSubstrNoRepeats("havefunonleetcode", 5)) -> 6
← Back to All Questions