Introduction

Finding the smallest substring in a given string that contains both uppercase and lowercase versions of the same character is a practical string manipulation problem. It tests your understanding of the sliding window technique, character mapping, and efficient search strategies. This article walks through the problem definition, solution approach, and a working implementation.

Understanding the Problem

Given a string, find the smallest contiguous window (substring) such that for every letter in the window that appears in one case, the opposite case of that same letter also appears within the window.

For example, given the string aAbBcC, valid pairs include aA, bB, and cC. The smallest window containing at least one complete pair is aA (length 2). For the string abcABCabc, the smallest window containing all pairs aA, bB, cC would be cABC (length 4).

A key clarification: we only need to satisfy pairs for characters that actually appear in the window. The goal is to find a window where every letter present has both its cases represented.

Approach: Sliding Window with Hash Map

The sliding window technique is ideal here because we need a contiguous substring that satisfies a condition, and we want the minimum-length one.

Algorithm Steps

1. Expand the window by moving the end pointer to the right, adding characters to a frequency map.
2. Check validity: For every character in the current window, verify that both its uppercase and lowercase forms are present. Use ASCII arithmetic to toggle between cases. The difference between lowercase and uppercase for English letters is 32: ord('a') - ord('A') = 32.
3. Contract the window by moving the start pointer to the right while the window remains valid. Track the minimum window length.
4. Record the answer whenever a valid window is found that is smaller than the current best.

Implementation

1def smallest_window_with_case_pairs(s):
2    n = len(s)
3    best_start = 0
4    best_len = float('inf')
5
6    for start in range(n):
7        freq = {}
8        for end in range(start, n):
9            ch = s[end]
10            freq[ch] = freq.get(ch, 0) + 1
11
12            # Check if current window is valid
13            valid = True
14            for c in freq:
15                if c.isalpha():
16                    pair = c.swapcase()
17                    if pair not in freq:
18                        valid = False
19                        break
20
21            if valid and (end - start + 1) < best_len:
22                best_len = end - start + 1
23                best_start = start
24
25    if best_len == float('inf'):
26        return ""
27    return s[best_start:best_start + best_len]

This brute-force version runs in $O(n^2 \cdot k)$ time where $k$ is the number of distinct characters in the window. For most practical inputs this is acceptable, but we can optimize further.

Optimized Sliding Window

1def smallest_window_optimized(s):
2    n = len(s)
3    best = ""
4    start = 0
5    freq = {}
6
7    def is_valid():
8        for c in freq:
9            if freq[c] > 0 and c.isalpha():
10                if freq.get(c.swapcase(), 0) <= 0:
11                    return False
12        return True
13
14    for end in range(n):
15        ch = s[end]
16        freq[ch] = freq.get(ch, 0) + 1
17
18        while is_valid():
19            window_len = end - start + 1
20            if best == "" or window_len < len(best):
21                best = s[start:end + 1]
22            freq[s[start]] -= 1
23            start += 1
24
25    return best

This optimized version uses a true sliding window that avoids restarting from every position. The start pointer only moves forward, giving an amortized $O(n \cdot k)$ time complexity.

Worked Example

Consider the string "aASFabcdSgAB".

The first valid window found is aA with length 2. The algorithm continues scanning to see if any single-pair window of length 2 exists elsewhere, but aA at the start is already minimal.

For a string like "xXyYzZ", every two-character pair is valid, so the answer is length 2 (the first pair xX).

Edge Cases

• No valid window exists: If the string contains only uppercase or only lowercase letters, return an empty string.
• Single character: A single character can never form a valid pair.
• All identical pairs adjacent: The minimum window is always 2 in this case.

Time and Space Complexity

Here $n$ is the string length and $k$ is the number of distinct characters in the current window (at most 52 for English letters).

Summary

The sliding window technique is the natural fit for this problem. By maintaining a frequency map and checking that every letter in the window has its case counterpart, you can efficiently find the smallest valid substring. The key insight is using swapcase() or ASCII arithmetic (add or subtract 32) to toggle between cases, and contracting the window from the left whenever the validity condition holds.