Given an array of unique charactersarrand a stringstr, Implement a functiongetShortestUniqueSubstringthat finds the smallest substring ofstrcontaining all the characters inarr. 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"

ANSWER: 2 pointer + Map

import java.io.*;
import java.util.*;

class Solution {

  static String getShortestUniqueSubstring(char[] arr, String str) {
    if (str.length() == 0) {
      return "";
    }
    HashMap<Character, Integer> track = new HashMap<>();
    HashSet<Character> set = new HashSet<>();
    for (char i : arr) {
      set.add(i);
    }
    int minSize = str.length();
    int finalLeft = -1;
    int finalRight = -1;
    int leftPointer = 0;
    int rightPointer = 1;
    track.put(str.charAt(leftPointer), 1);
    int n = str.length();
    while (rightPointer <= n - 1 && rightPointer != leftPointer) {
      if (track.size() != arr.size()) {
          char currChar = str.charAt(rightPointer);
        if (set.contains(currChar)) {
            if (!track.contains(currChar)) {
                  track.put(currChar, 1);
                } else {
                  track.put(currChar, track.get(currChar) + 1);
                }
        }
        rightPointer++;
      } else {
        int currSize = rightPointer - leftPointer + 1;
        if (currSize < minSize) {
          minSize = currSize;
          finalLeft = leftPointer;
          finalRight = rightPointer;
        }
        while (track.size() != n && leftPointer < rightPointer) {
          char currLeft = str.charAt(leftPointer);
          if (track.get(currLeft) == 1) {
            track.remove(currLeft);
          } else {
            track.put(currLeft, track.get(currLeft) - 1);
          }
          leftPointer++;
        }
      }
    }
    if (finalLeft >= 0) {
      return str.substring(finalLeft, finalRight + 1);
    }
    return "";
  }

  public static void main(String[] args) {

  }

}