Pramp – Smallest Substring of All Characters

Question

Given an array of unique characters arr and a string str, Implement a function getShortestUniqueSubstring that finds the smallest substring of str containing all the characters in arr. Return “” (empty string) if such a substring doesn’t exist.

Come up with an asymptotically optimal solution and analyze the time and space complexities.

Example

input: arr = ['x','y','z'], str = "xyyzyzyx"
output: "zyx"

Constraints

• [time limit] 5000ms
• [input] array.character arr
  1 ≤ arr.length ≤ 30
• [input] string str
  1 ≤ str.length ≤ 500
• [output] string

Solutions

Time Complexity: O(max(len(arr), len(str)))
Worst Space Complexity: O(len(arr))

def get_shortest_unique_substring(arr, str):
  arr_set = set(arr)
  smallest_str = ""
  i = 0
  # if smallest substring of all characters exists
  # its length should be len(arr) at least
  while i < len(str) - len(arr_set) +1:
    appeared_alphabets = set()
    for j in range(i, len(str)):
      if str[j] in arr_set:
        appeared_alphabets.add(str[j])
        if len(appeared_alphabets) == len(arr):
          cur_smallest_str = str[i: j + 1]

          if len(cur_smallest_str) == len(arr_set):
            return cur_smallest_str

          if len(smallest_str) > len(cur_smallest_str) or smallest_str == "":
            smallest_str = cur_smallest_str
                  
        latest_c = set(str[j])
        for k in range(j - 1, i + 1, -1):
          if str[k] in latest_c:
            i = k
            break
          else:
            latest_c.add(str[k])
        break
          
    i += 1
  return smallest_str

Last Updated on 2023/08/16 by A1go