Understanding the Shortest Substring Problem
The HackerRank "ShortestSubstring" problem asks you to find the smallest window in a string that contains all characters of a target string. It shows up in the medium-difficulty section and tests whether you actually understand sliding window patterns or if you can only follow tutorials by rote. When I first saw this problem, I wrote a brute force solution that checked every possible substring. For a string of length 1000, it ran in about 47 seconds. The judge rejected it for timeout, which wasn't surprising. What surprised me was the test case that broke my second attempt: a target string with duplicate characters where the duplicates were positioned at the very edges of the source string. I spent two days debugging before I realized I was decrementing my character count incorrectly when the window contracted. The standard approach uses two pointers, left and right, both starting at the beginning of the source string. You expand the right pointer to include characters until your window contains all required characters. Then you contract the left pointer to find the smallest valid window. Repeat until right reaches the end.
Here's how the logic actually plays out in code: First, you build a frequency map of the target string characters. This tells you exactly what you need to find. Then you maintain a separate counter for how many unique characters from the target you've currently matched in your window. When matched equals the number of unique target characters, your window is valid and you try to shrink it. I wrote this in Python because the hash map syntax is clean enough:
from collections import Counter
def shortest_window(source, target):
target_count = Counter(target)
required = len(target_count)
left = right = 0
formed = 0
window_counts = {}
result = (0, float('inf'))
while right < len(source):
char = source[right]
window_counts[char] = window_counts.get(char, 0) + 1
if char in target_count and window_counts[char] == target_count[char]:
formed += 1
while formed == required:
if right - left + 1 < result[1]:
result = (left, right)
left_char = source[left]
window_counts[left_char] -= 1
if left_char in target_count and window_counts[left_char] < target_count[left_char]:
formed -= 1
left += 1
right += 1
return result[1] == float('inf') and "" or source[result[0]:result[1]+1]
Get the Full Details
Why This Pattern trips People Up
The condition that checks whether formed should increment or decrement is where most solutions fail. You only increment formed when a character's count in the window EXACTLY matches its required count. Not when it exceeds it. And you only decrement formed when dropping a character makes the count FALL BELOW the required amount. I see this mistake constantly. Someone writes window_counts[char] >= target_count[char] for the increment check, which causes formed to spike incorrectly when there are extra copies of a character in the window. The window never properly contracts because formed stays above required even when the window is missing characters.
A Note on Edge Cases I've Hit Repeatedly
One specific issue: when the target string contains characters not present in the source at all. Your solution should return an empty string or some sentinel value, but HackerRank's test suite expects a specific format. I learned this the hard way after submitting three times. Check what the problem statement actually says about the return format when no valid window exists. Some versions expect "-1" as a string, others expect an empty string, and the problem description on the page can change between versions without warning. Another edge case is when the target is longer than the source. A naive solution might still run through the entire algorithm. Adding a guard clause at the top — if len(target) > len(source): return "" — cuts off those cases immediately and saves computational cycles.
Complexity Analysis
This runs in O(n) time where n is the length of the source string. Each character gets visited at most twice: once when the right pointer includes it and once when the left pointer excludes it. The space complexity is O(m) where m is the number of unique characters in the target string, since that's what the hash maps store. For a source string of 100,000 characters, this approach takes roughly 0.12 seconds on my machine. The brute force version I mentioned earlier would have needed around 30 seconds or more. The difference isn't just academic — HackerRank has strict time limits that these constraints enforce.
When This Approach Falls Apart
The sliding window technique assumes that contracting a valid window never creates a new valid window. That's generally true for this problem, but if you modify the requirements — say, asking for minimum windows containing at least k distinct characters instead of all characters — the approach needs adjustment. The greedy contraction doesn't always work in those variants because shrinking the window might still leave you with enough distinct characters, creating multiple valid windows at different sizes. For the standard HackerRank version, this method is optimal. If you're working on a variation where the greedy property breaks down, you'd need a different strategy like binary search on the answer combined with a frequency check, which pushes the complexity to O(n log n).
Shortest Substring Hackerrank Solution
If you're implementing this yourself, make sure to test against strings with repeated characters, single-character targets, and cases where the answer is the entire source string. The hidden test cases on HackerRank tend to favor the less obvious scenarios. I've found that writing a small test runner that generates random source and target pairs and compares your output against a brute force reference implementation catches most bugs before you submit. My local test suite runs about 200 randomized cases in under a second and has caught issues that the public samples missed every time.
