MiddleCodeOccasionalNot answered yet
Shortest substring containing every letter of a given alphabet
Given an alphabet (a set of required characters) and a string, find the shortest substring of the string that contains every character of the alphabet (extra characters are allowed), or report that none exists.
Requirements:
- O(n) time over the string length.
- Must consider windows ending at the very last character.
// returns {start, length} of the shortest covering window, or {-1, 0} if none
std::pair<int,int> minPangram(const std::string& s, const std::string& alphabet) {
// your code here
}Write the implementation.
Use a sliding window with a count of required characters still missing, kept in a hash map. Expand right, decrementing the count when a needed char is first covered. While the window covers all required chars, record it if shorter and shrink from left. Run to the end so a window ending at the last char counts.
- ✗Expanding the window but never shrinking from the left to minimise it
- ✗Stopping early and missing a window that ends at the last character
- ✗Not reporting failure when the alphabet is never fully covered
- →How does the missing-count let you check coverage in O(1) per step?
- →How does the answer change if extra characters are not allowed?
Contents
Task
Find the shortest substring covering all alphabet letters in O(n) (or report none).
Solution
#include <string>
#include <unordered_map>
#include <utility>
std::pair<int,int> minPangram(const std::string& s, const std::string& alphabet) {
std::unordered_map<char,int> need;
for (char c : alphabet) ++need[c];
int missing = (int)need.size(); // how many chars not yet covered
int left = 0, bestStart = -1, bestLen = INT_MAX;
for (int right = 0; right < (int)s.size(); ++right) {
if (--need[s[right]] == 0) --missing; // a character fully covered
while (missing == 0) { // window covers the alphabet
if (right - left + 1 < bestLen) { bestLen = right - left + 1; bestStart = left; }
if (++need[s[left]] > 0) ++missing; // shrink from the left
++left;
}
}
return bestStart < 0 ? std::make_pair(-1, 0) : std::make_pair(bestStart, bestLen);
}Key points
- The
missingcounter checks coverage in O(1) per step. - The window both expands and shrinks — otherwise the minimum is missed.
- Running to the end catches windows that end at the last character.
Contents
