Smallest window containing all distinct characters of itself

Medium

Problem

Return the length of the smallest substring that contains every distinct character of the whole string.

Example 1

Input:  "aabcbcdbca"
Output: 4

"dbca" contains a, b, c and d.

Also asked as: Write a program tofind the smallest window that contains all characters of string itself

Test cases

Case 1

Input:    "aabcbcdbca"
Expected: 4

Case 2

Input:    "aaab"
Expected: 2

Case 3

Input:    "abc"
Expected: 3

Case 4

Input:    "aaaa"
Expected: 1

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Sliding window over the distinct-count target

Time O(n)Space O(k)

Target = number of distinct characters in the whole string. Expand right until the window has them all, then contract left.

function smallestDistinctWindow(s) {
const target = new Set(s).size;
const count = new Map();
let have = 0, start = 0, best = s;
for (let end = 0; end < s.length; end++) {
const c = s[end];
count.set(c, (count.get(c) || 0) + 1);
if (count.get(c) === 1) have++;
while (have === target) {
if (end - start + 1 < best.length) best = s.slice(start, end + 1);
const lc = s[start++];
count.set(lc, count.get(lc) - 1);
if (count.get(lc) === 0) have--;
}
}
return best.length;
}