Skip to content

Instantly share code, notes, and snippets.

@erikseulean
Created February 5, 2018 17:35
Show Gist options
  • Select an option

  • Save erikseulean/a30654811c876a9ba32e42bdf7e2dcbf to your computer and use it in GitHub Desktop.

Select an option

Save erikseulean/a30654811c876a9ba32e42bdf7e2dcbf to your computer and use it in GitHub Desktop.
Shortest substring containing all
def shortest_substring(words, text):
total, start, mstart, mend = 0, 0, 0, 0
min_value = len(text)
counts = defaultdict(int)
for i in range(len(text)):
if text[i] in words:
counts[text[i]] = counts[text[i]] + 1
if counts[text[i]] == 1:
total = total + 1
while total == len(words):
if min_value > i - start:
min_value = i - start
mstart, mend = start, i
if text[start] in words:
counts[text[start]] = counts[text[start]] - 1
if counts[text[start]] < 1:
total = total - 1
start = start + 1
while text[start] not in words:
start = start + 1
return text[mstart: mend + 1]
print(shortest_substring(set(['a', 'b', 'd']), 'abcefddalmbd'))
print(shortest_substring(set(['a', 'b', 'c']), 'mbalmpdabcl'))
print(shortest_substring(set(['a', 'b', 'c']), 'mbalmpdampzzzbcla'))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment