find-shortest-substring
An interview problem designed to assess coding skills and understanding of complexity
Rephrased version of the Minimum Window Substring puzzle
The problem
Given two strings, find the shortest substring of the first string that contains all letters of the second one. Count matters. Examples:
"AAAAABBBB", "BAB" -> "ABB"
"AAABBBCCC", "ABC" -> "ABBBC"
"THELONGTEXT", "ETT" -> "TEXT"
Implementation
- O(n) CPU / O(n) memory solution based on two hashmaps and two sliding window pointers
- Written in JavaScript targeting ECMAScript 2015 or newer environments
- Code style favors readability over compactness