# OA | Substring of Size K with K Distinct Characters

Reference: OA
Difficulty: Medium

## Problem

Given a string s and an int k, return all unique substrings of s of size k with k distinct characters.

Note:

• The input string consists of only lowercase English letters [a-z].
• 0 ≤ k ≤ 26

Example:

## Analysis

Playground: https://leetcode.com/playground/VsNDKQoK

### Brute-Force

For each possible substrings, check if it is distinct.

Note: Strings in result are distinct too.

Time: $O(kN)$ where $N$ is the length of the string.
Space: $O(kN)$ since we need to store the result.

### Sliding Window

Consider the follow examples for the sliding window to see why it works.

start and end denote the range of the window. Particularly, end is the cursor that from 0 to n - 1.

Time: $O(kN)$
Space: $O(kN)$

Comment
Junhao Wang
a software engineering cat