Word Letter Span - Find Shortest Substring Containing All Target Letters
Question Details
Round 1 Coding
Problem
Given a string s and a list of target characters targets, find the shortest contiguous substring of s that contains all characters in targets (each at least once). If no such substring exists,
return an empty string.
python
def word_letter_span(s: str, targets: list[str]) -> str:
**Returns** shortest substring of s containing all chars in targets
# If multiple substrings have the same minimum length,
**return** the leftmost
...
**Example**:
word_letter_span("adobecodebanc", ["a","b","c"]) -> "banc"
word_letter_span("aa", ["a","a"]) -> "aa"
word_letter_span("xyz", ["a"]) -> ""
Approach
Sliding window with two pointers. Maintain a frequency map of needed characters. Expand the right pointer until all targets are covered, then shrink the left pointer to minimize the window.
python
from collections import Counter
def word_letter_span(s: str, targets: list[str]) -> str:
need = Counter(targets)
have, required = {}, len(need)
formed = 0
l, best = 0, ""
for r, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if not best or r - l + 1 < len(best):
best = s[l:r+1]
lc = s[l]
have[lc] -= 1
if lc in need and have[lc] < need[lc]:
formed -= 1
l += 1
**return** best
Follow-ups
- What is the time and space complexity?
- How does the solution handle duplicate characters in
targets? - How would you modify this to find all minimal-length windows, not just the first?
- How would you extend this to work on a list of words instead of characters?
Full Details
Round 1 Coding
Problem
Given a string s and a list of target characters targets, find the shortest contiguous substring of s that contains all characters in targets (each at least once). If no such substring exists,
return an empty string.
python
def word_letter_span(s: str, targets: list[str]) -> str:
**Returns** shortest substring of s containing all chars in targets
# If multiple substrings have the same minimum length,
**return** the leftmost
...
**Example**:
word_letter_span("adobecodebanc", ["a","b","c"]) -> "banc"
word_letter_span("aa", ["a","a"]) -> "aa"
word_letter_span("xyz", ["a"]) -> ""
Approach
Sliding window with two pointers. Maintain a frequency map of needed characters. Expand the right pointer until all targets are covered, then shrink the left pointer to minimize the window.
python
from collections import Counter
def word_letter_span(s: str, targets: list[str]) -> str:
need = Counter(targets)
have, required = {}, len(need)
formed = 0
l, best = 0, ""
for r, c in enumerate(s):
have[c] = have.get(c, 0) + 1
if c in need and have[c] == need[c]:
formed += 1
while formed == required:
if not best or r - l + 1 < len(best):
best = s[l:r+1]
lc = s[l]
have[lc] -= 1
if lc in need and have[lc] < need[lc]:
formed -= 1
l += 1
**return** best
Follow-ups
- What is the time and space complexity?
- How does the solution handle duplicate characters in
targets? - How would you modify this to find all minimal-length windows, not just the first?
- How would you extend this to work on a list of words instead of characters?
About This Question
This is a reported interview question from a upstart interview during the phone round.
It covers the following topics: Strings, Sliding Window, Phone, Coding, Onsite .