Find minimum substring - Being interviewer - May 4 2018

FindMinimumSubstring_BeingInterviewer.java

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

class Solution {
  /*
  Input: xyyzyzyx
  
  All substring O(n*n) substrings * check each subtring O(m) = O(n*n*m): 
    x y y z y z y x
    xy yy yz zy yz zy yx
    xyy yyz yzy zyz yzz zyy
    Max of O(n*n+n*m)
    
    
  */
  static String getShortestUniqueSubstring(char[] arr, String str) {
    if(arr.length == 0) {
      return "";
    }
    // your code goes here
    Set<Character> inp = new HashSet<Character>();
    for(char ch : arr) {
      inp.add(ch);
    }
    String minString = "";
    for(int i = 0; i < str.length() - arr.length; i++) {
      Set<Character> check = new HashSet<>();
      check.addAll(inp);
      for(int j = i; j < str.length(); ++j) {
        check.remove(str.charAt(j));
        if(check.isEmpty()) {
          String cand = str.substring(i, j+1);
          if(cand.length() < minString.length()) {
            minString = cand;
          }
          break;
        }
      }
    }
    return minString;
  }

  public static void main(String[] args) {

  }

}

/*
AAAAABC
|     |  -> "AAAAABC"
             ||||
                 ABC 
n^n 
using previous knowledge 
ABABC
----->
 ---->
 
 O(n)
 
 
ABC
*/