Problem

Given a string s, find the shortest substring (window) that contains every distinct character that appears in s at least once. Return the substring (or its length).

Examples

Example 1

1
2

Input: s = "aabcbcdbca"
Output: "dbca"  // length 4

Example 2

1
2

Input: s = "aaab"
Output: "ab"    // length 2
Similar Problems

Solution

We can solve this with a sliding-window (two-pointer) technique and a frequency table that tracks how many distinct characters inside the current window have non-zero counts.

Method 1 — Sliding window counting distinct characters

Intuition

If the string has k distinct characters overall, any valid window must contain at least one occurrence of each of those k characters. Expand the right end to include characters until the window contains all k distinct characters, then shrink from the left to remove redundant characters and record the smallest valid window seen.

Approach

  1. Precompute k = number of distinct characters in s (by scanning once).
  2. Use an array or map freq to track character counts inside the current window, two pointers l = 0, r = 0, and count = 0 which counts how many distinct characters in the window currently have count >= 1.
  3. Expand r from 0..n-1:
    • Increment freq[s[r]]; if its new count is 1, increment count.
    • While count == k, try to shrink the window from the left:
      • Update best window if current length r-l+1 is smaller.
      • Decrement freq[s[l]]; if freq[s[l]] becomes 0, decrement count.
      • Increment l.
  4. At the end best holds the smallest window (or its length).

Edge cases:

  • Empty string -> return empty substring / length 0.
  • All characters the same -> shortest window is of length 1.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

#include <string>
#include <vector>
#include <limits>

class Solution {
 public:
  std::string smallestWindow(const std::string &s) {
    if (s.empty()) return "";
    const int ALPHA = 256;
    std::vector<int> seen(ALPHA, 0);
    int distinct = 0;
    for (unsigned char c : s) if (seen[c]++ == 0) ++distinct;

    std::vector<int> freq(ALPHA, 0);
    int count = 0; // distinct characters in window
    int l = 0;
    int bestLen = std::numeric_limits<int>::max();
    int bestStart = 0;

    for (int r = 0; r < (int)s.size(); ++r) {
      unsigned char c = s[r];
      if (freq[c]++ == 0) ++count;
      while (count == distinct) {
        if (r - l + 1 < bestLen) {
          bestLen = r - l + 1;
          bestStart = l;
        }
        unsigned char lc = s[l];
        if (--freq[lc] == 0) --count;
        ++l;
      }
    }
    return bestLen == std::numeric_limits<int>::max() ? std::string() : s.substr(bestStart, bestLen);
  }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

package main

import "math"

func smallestWindow(s string) string {
  if len(s) == 0 { return "" }
  const ALPHA = 256
  var seen [ALPHA]int
  distinct := 0
  for i := 0; i < len(s); i++ {
    b := s[i]
    if seen[b] == 0 { distinct++ }
    seen[b]++
  }

  var freq [ALPHA]int
  count := 0
  l := 0
  bestLen := math.MaxInt32
  bestStart := 0
  for r := 0; r < len(s); r++ {
    b := s[r]
    if freq[b] == 0 { count++ }
    freq[b]++
    for count == distinct {
      if r-l+1 < bestLen {
        bestLen = r-l+1
        bestStart = l
      }
      lb := s[l]
      freq[lb]--
      if freq[lb] == 0 { count-- }
      l++
    }
  }
  if bestLen == math.MaxInt32 { return "" }
  return s[bestStart:bestStart+bestLen]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
  public String smallestWindow(String s) {
    if (s == null || s.isEmpty()) return "";
    final int ALPHA = 256;
    int[] seen = new int[ALPHA];
    int distinct = 0;
    for (int i = 0; i < s.length(); ++i) if (seen[s.charAt(i)]++ == 0) ++distinct;

    int[] freq = new int[ALPHA];
    int count = 0, l = 0;
    int bestLen = Integer.MAX_VALUE, bestStart = 0;
    for (int r = 0; r < s.length(); ++r) {
      if (freq[s.charAt(r)]++ == 0) ++count;
      while (count == distinct) {
        if (r - l + 1 < bestLen) { bestLen = r - l + 1; bestStart = l; }
        if (--freq[s.charAt(l)] == 0) --count;
        ++l;
      }
    }
    return bestLen == Integer.MAX_VALUE ? "" : s.substring(bestStart, bestStart + bestLen);
  }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution:
  def smallestWindow(self, s: str) -> str:
    if not s:
      return ""
    ALPHA = 256
    seen = [0] * ALPHA
    distinct = 0
    for ch in s:
      b = ord(ch)
      if seen[b] == 0:
        distinct += 1
      seen[b] += 1

    freq = [0] * ALPHA
    count = 0
    l = 0
    best_len = float('inf')
    best_start = 0
    for r, ch in enumerate(s):
      b = ord(ch)
      if freq[b] == 0:
        count += 1
      freq[b] += 1
      while count == distinct:
        if r - l + 1 < best_len:
          best_len = r - l + 1
          best_start = l
        lb = ord(s[l])
        freq[lb] -= 1
        if freq[lb] == 0:
          count -= 1
        l += 1
    return "" if best_len == float('inf') else s[best_start:best_start+best_len]

Complexity

  • ⏰ Time complexity: O(n) — each character is visited at most a constant number of times while expanding and contracting the window.
  • 🧺 Space complexity: O(k) where k is the alphabet size (here k = 256 for ASCII); if using dynamic maps the space is O(min(n, alphabet)).