Smallest window containing all distinct characters of itself
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
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;}