Problem

Given strings str1 and str2, find the minimum (contiguous) substring sub_str of str1, such that every character of str2 appears in sub_str in the same order as it is present in str2.

Solution

def min_substring(str1, str2):
    if not str1 or not str2:
        return ""

    # Initialize the hashmap
    hashmap = {}
    for char in str2:
        hashmap[char] = 0

    # Initialize the sliding window
    start = 0
    end = 0
    min_len = float('inf')
    min_start = 0
    min_end = 0
    count = 0

    # Move end to find a valid substring
    while end < len(str1):
        # If char is in hashmap, decrease the count
        if str1[end] in hashmap:
            hashmap[str1[end]] -= 1
            if hashmap[str1[end]] >= 0:
                count += 1

        # If we found a valid substring, try to minimize it
        while count == len(str2):
            # Update minimum length substring if needed
            if end - start + 1 < min_len:
                min_len = end - start + 1
                min_start = start
                min_end = end

            # If char is in hashmap, increase the count
            if str1[start] in hashmap:
                hashmap[str1[start]] += 1
                if hashmap[str1[start]] > 0:
                    count -= 1

            # Move start to find smaller substring
            start += 1

        # Move end to find a valid substring
        end += 1

    if min_len == float('inf'):
        return ""
    return str1[min_start:min_end + 1]


print(min_substring("ADOBECODEBANC", "ABC"))
# BANC