Find K-Length Substrings With No Repeated Characters

Find K-Length Substrings With No Repeated Characters - Problem

Given a string s and an integer k, return the number of substrings in s of length k with no repeated characters.

A substring is a contiguous sequence of characters within a string.

Example:

If s = "havefunonleetcode" and k = 5, the substring "havef" has repeated character 'e', but "onlee" has repeated 'e', while "funon" has no repeated characters.

Input & Output

Example 1 — Basic Case

$ Input: s = "havefunonleetcode", k = 5

› Output: 6

💡 Note: The valid substrings are: "havef" (no duplicates), "avefe" (no duplicates), "vefun" (no duplicates), "efuno" (no duplicates), "funon" (no duplicates), "unon" has duplicate 'n', "nonl" has duplicate 'n', continuing this way we find 6 valid substrings.

Example 2 — Shorter String

$ Input: s = "home", k = 3

› Output: 2

💡 Note: The substrings are: "hom" (all unique), "ome" (all unique). Both have no repeated characters, so answer is 2.

Example 3 — All Same Characters

$ Input: s = "aaa", k = 2

› Output: 0

💡 Note: All possible substrings of length 2 are "aa" which has repeated character 'a', so no valid substrings exist.

Constraints

1 ≤ s.length ≤ 10⁴
1 ≤ k ≤ 26
s consists of lowercase English letters only

Visualization

Tap to expand

Understanding the Visualization

Input

String s and integer k

Process

Check each k-length substring for unique characters

Output

Count of valid substrings

Key Takeaway

🎯 Key Insight: Use sliding window with hash map to efficiently track character frequencies in O(n) time

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is to use a sliding window approach with a hash map to efficiently track character frequencies. The optimal solution maintains a window of size k and counts unique characters in O(n) time with O(k) space. Best approach is sliding window: Time: O(n), Space: O(k)

Common Approaches

Approach	Time	Space	Notes
✓ Sliding Window with Hash Set	O(n)	O(k)	Use a sliding window of size k with a hash set to track unique characters
Brute Force - Check All Substrings	O(n×k²)	O(1)	Generate all substrings of length k and check each for duplicate characters

Sliding Window with Hash Set — Algorithm Steps

Initialize a hash set and character frequency map
Process the first k characters to form initial window
Slide window one position at a time
Update frequency map and check if window has k unique characters
Count valid windows

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Window

Set up first k characters with frequency map

Slide Window

Add new character, remove old character

Check Uniqueness

Count valid windows with k unique characters

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <stdbool.h>

#define MAX_CHARS 256

int solution(char* s, int k) {
    int n = strlen(s);
    if (k > n) {
        return 0;
    }
    
    int count = 0;
    int charCount[MAX_CHARS] = {0};
    int uniqueChars = 0;
    
    // Initialize first window
    for (int i = 0; i < k; i++) {
        if (charCount[s[i]] == 0) {
            uniqueChars++;
        }
        charCount[s[i]]++;
    }
    
    // Check if first window is valid
    if (uniqueChars == k) {
        count++;
    }
    
    // Slide the window
    for (int i = k; i < n; i++) {
        // Add new character
        if (charCount[s[i]] == 0) {
            uniqueChars++;
        }
        charCount[s[i]]++;
        
        // Remove old character
        char oldChar = s[i - k];
        charCount[oldChar]--;
        if (charCount[oldChar] == 0) {
            uniqueChars--;
        }
        
        // Check if current window is valid
        if (uniqueChars == k) {
            count++;
        }
    }
    
    return count;
}

int main() {
    char s[1000];
    int k;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;  // Remove newline
    
    scanf("%d", &k);
    
    int result = solution(s, k);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each character is added and removed from set at most once

✓ Linear Growth

Space Complexity

O(k)

Hash set stores at most k characters from the current window

✓ Linear Space

28.5K Views

Medium Frequency

~15 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Sliding Window with Hash Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler