strings.min_window_substring

Functions

min_window(→ str)

Given a string to search, and another string of target char_dict,

Module Contents

strings.min_window_substring.min_window(search_str: str, target_letters: str) → str

Given a string to search, and another string of target char_dict, return the smallest substring of the search string that contains all target char_dict.

This is somewhat modified from my solution to the problem “Minimum Window Substring” on leetcode. https://leetcode.com/problems/minimum-window-substring/description/

>>> min_window("Hello World", "lWl")
'llo W'
>>> min_window("Hello World", "f")
''

This solution uses a sliding window, alternating between shifting the end of the window right until all target char_dict are contained in the window, and shifting the start of the window right until the window no longer contains every target character.

Time complexity: O(target_count + search_len) ->

The algorithm checks a dictionary at most twice for each character in search_str.

Space complexity: O(search_len) ->

The primary contributor to additional space is the building of a dictionary using the search string.