Как найти наименьшую подстроку, содержащую все символы заданной строки?

Чтобы увидеть более подробную информацию, включая рабочий код, проверьте мой пост в блоге по адресу:

http://www.leetcode.com/2010/11/finding-minimum-window-in-s-what.html

Чтобы проиллюстрировать этот подход, я использую пример: строка1 = "acbbaca" и строка2 = "aba". Здесь мы также используем термин «окно», который означает непрерывный блок символов из строки1 (может быть заменен термином подстрока).

i) строка1 = "acbbaca" и строка2 = "aba".

ii) Найдено первое минимальное окно. Обратите внимание, что мы не можем продвигать начальный указатель, поскольку hasFound['a'] == needToFind['a'] == 2. Продвижение означало бы нарушение ограничения.

iii) Второе окно найдено. Указатель начала по-прежнему указывает на первый элемент 'a'. hasFound['a'] (3) больше, чем needToFind['a'] (2). Мы уменьшаем hasFound['a'] на единицу и перемещаем указатель начала вправо.

iv) Мы пропускаем 'c', так как он не найден в строке2. Указатель начала теперь указывает на «b». hasFound['b'] (2) больше, чем needToFind['b'] (1). Мы уменьшаем hasFound['b'] на единицу и перемещаем указатель начала вправо.

v) Указатель начала теперь указывает на следующую букву «b». hasFound['b'] (1) равно needToFind['b'] (1). Мы немедленно останавливаемся, и это наше вновь найденное минимальное окно.

Идея в основном основана на помощи двух указателей (начало и конец окна) и двух таблиц (needToFind и hasFound) при обходе строки1. needToFind сохраняет общее количество символов в строке2, а hasFound сохраняет общее количество встреченных символов. Мы также используем переменную счетчика для хранения всех встреченных символов в строке 2 (не считая символов, где hasFound[x] превышает needToFind[x]). Когда count равен длине string2, мы знаем, что найдено допустимое окно.

Каждый раз, когда мы продвигаем конечный указатель (указывающий на элемент x), мы увеличиваем hasFound[x] на единицу. Мы также увеличиваем count на единицу, если hasFound[x] меньше или равно needToFind[x]. Почему? Когда ограничение соблюдено (то есть, count равно размеру string2), мы немедленно перемещаем указатель начала вправо насколько возможно, сохраняя при этом ограничение.

Как проверить, соблюдается ли ограничение? Предположим, что begin указывает на элемент x. Мы проверяем, больше ли hasFound[x], чем needToFind[x]. Если это так, мы можем уменьшить hasFound[x] на единицу и сдвинуть указатель начала, не нарушая ограничения. С другой стороны, если это не так, мы немедленно останавливаемся, поскольку продвижение указателя начала нарушает ограничение окна.

Наконец, мы проверяем, меньше ли минимальная длина окна текущего минимума. Обновите текущий минимум, если найден новый минимум.

По сути, алгоритм находит первое окно, удовлетворяющее ограничению, а затем продолжает поддерживать ограничение на протяжении всего окна.

Вот решение O (n). Основная идея проста: для каждого начального индекса найти наименьший конечный индекс, чтобы подстрока содержала все необходимые буквы. Хитрость заключается в том, что индекс с наименьшим конечным номером увеличивается в ходе выполнения функции, поэтому при небольшой поддержке структуры данных мы рассматриваем каждый символ не более двух раз.

В Питоне:

from collections import defaultdict

def smallest(s1, s2):
    assert s2 != ''
    d = defaultdict(int)
    nneg = [0]  # number of negative entries in d
    def incr(c):
        d[c] += 1
        if d[c] == 0:
            nneg[0] -= 1
    def decr(c):
        if d[c] == 0:
            nneg[0] += 1
        d[c] -= 1
    for c in s2:
        decr(c)
    minlen = len(s1) + 1
    j = 0
    for i in xrange(len(s1)):
        while nneg[0] > 0:
            if j >= len(s1):
                return minlen
            incr(s1[j])
            j += 1
        minlen = min(minlen, j - i)
        decr(s1[i])
    return minlen

Я получил тот же вопрос интервью. Я являюсь кандидатом на C++, но я мог относительно быстро писать код на JAVA.

Java [Предоставлено Sumod Mathilakath]

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

class UserMainCode
{


    public String GetSubString(String input1,String input2){
        // Write code here...
        return find(input1, input2);
    }
  private static boolean containsPatternChar(int[] sCount, int[] pCount) {
        for(int i=0;i<256;i++) {
            if(pCount[i]>sCount[i])
                return false;
        }
        return true;
    }
  public static String find(String s, String p) {
        if (p.length() > s.length())
            return null;
        int[] pCount = new int[256];
        int[] sCount = new int[256];
        // Time: O(p.lenght)
        for(int i=0;i<p.length();i++) {
            pCount[(int)(p.charAt(i))]++;
            sCount[(int)(s.charAt(i))]++;
        }
        int i = 0, j = p.length(), min = Integer.MAX_VALUE;
        String res = null;
        // Time: O(s.lenght)
        while (j < s.length()) {
            if (containsPatternChar(sCount, pCount)) {
                if ((j - i) < min) {
                    min = j - i;
                    res = s.substring(i, j);
                    // This is the smallest possible substring.
                    if(min==p.length())
                        break;
                    // Reduce the window size.
                    sCount[(int)(s.charAt(i))]--;
                    i++;
                }
            } else {
                sCount[(int)(s.charAt(j))]++;
                // Increase the window size.
                j++;
            }
        }
        System.out.println(res);
        return res;
    }
}

C++ [Предоставлено sundeepblue]

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;
string find_minimum_window(string s, string t) {
    if(s.empty() || t.empty()) return;

    int ns = s.size(), nt = t.size();
    vector<int> total(256, 0);
    vector<int> sofar(256, 0);
    for(int i=0; i<nt; i++) 
        total[t[i]]++;

    int L = 0, R; 
    int minL = 0;                           //gist2
    int count = 0;
    int min_win_len = INT_MAX;

    for(R=0; R<ns; R++) {                   // gist0, a big for loop
        if(total[s[R]] == 0) continue;
        else sofar[s[R]]++;

        if(sofar[s[R]] <= total[s[R]])      // gist1, <= not <
            count++;

        if(count == nt) {                   // POS1
            while(true) {
                char c = s[L]; 
                if(total[c] == 0) { L++; }
                else if(sofar[c] > total[c]) {
                    sofar[c]--;
                    L++;
                }
                else break;
            }  
            if(R - L + 1 < min_win_len) {   // this judge should be inside POS1
                min_win_len = R - L + 1;
                minL = L;
            }
        }
    }
    string res;
    if(count == nt)                         // gist3, cannot forget this. 
        res = s.substr(minL, min_win_len);  // gist4, start from "minL" not "L"
    return res;
}
int main() {
    string s = "abdccdedca";
    cout << find_minimum_window(s, "acd");
}

Erlang [Предоставлено wardbekker]

-module(leetcode).

-export([min_window/0]).

%% Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

%% For example,
%% S = "ADOBECODEBANC"
%% T = "ABC"
%% Minimum window is "BANC".

%% Note:
%% If there is no such window in S that covers all characters in T, return the emtpy string "".
%% If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.



min_window() ->
    "eca" = min_window("cabeca", "cae"),
    "eca" = min_window("cfabeca", "cae"),
    "aec" = min_window("cabefgecdaecf", "cae"),
    "cwae" = min_window("cabwefgewcwaefcf", "cae"),
    "BANC" = min_window("ADOBECODEBANC", "ABC"),
    ok.

min_window(T, S) ->
    min_window(T, S, []).

min_window([], _T, MinWindow) ->
    MinWindow;
min_window([H | Rest], T, MinWindow) ->
    NewMinWindow = case lists:member(H, T) of
                       true ->
                           MinWindowFound = fullfill_window(Rest, lists:delete(H, T), [H]),
                           case length(MinWindow) == 0 orelse (length(MinWindow) > length(MinWindowFound)
                               andalso length(MinWindowFound) > 0) of
                               true ->
                                   MinWindowFound;
                               false ->
                                   MinWindow
                           end;
                       false ->
                           MinWindow
                   end,
    min_window(Rest, T, NewMinWindow).

fullfill_window(_, [], Acc) ->
    %% window completed
    Acc;
fullfill_window([], _T, _Acc) ->
    %% no window found
    "";
fullfill_window([H | Rest], T, Acc) ->
    %% completing window
    case lists:member(H, T) of
        true ->
            fullfill_window(Rest, lists:delete(H, T), Acc ++ [H]);
        false ->
            fullfill_window(Rest, T, Acc ++ [H])
    end.

ССЫЛКА:

• http://articles.leetcode.com/finding-minimum-window-in-s-what/#comment-511216
• http://www.mif.vu.lt/~valdas/ALGORITMAI/LITERATURA/Cormen/Cormen.pdf

Пожалуйста, взгляните и на это:

//-----------------------------------------------------------------------

bool IsInSet(char ch, char* cSet)
{
    char* cSetptr = cSet;
    int index = 0;
    while (*(cSet+ index) != '\0')
    {
        if(ch == *(cSet+ index))
        {
            return true;            
        }
        ++index;
    }
    return false;
}

void removeChar(char ch, char* cSet)
{
    bool bShift = false;
    int index = 0;
    while (*(cSet + index) != '\0')
    {
        if( (ch == *(cSet + index)) || bShift)
        {
            *(cSet + index) = *(cSet + index + 1);
            bShift = true;
        }
        ++index;
    }
}
typedef struct subStr
{
    short iStart;
    short iEnd;
    short szStr;
}ss;

char* subStringSmallest(char* testStr, char* cSet)
{
    char* subString = NULL;
    int iSzSet = strlen(cSet) + 1;
    int iSzString = strlen(testStr)+ 1;
    char* cSetBackUp = new char[iSzSet];
    memcpy((void*)cSetBackUp, (void*)cSet, iSzSet);

    int iStartIndx = -1;    
    int iEndIndx = -1;
    int iIndexStartNext = -1;

    std::vector<ss> subStrVec;
    int index = 0;

    while( *(testStr+index) != '\0' )
    {
        if (IsInSet(*(testStr+index), cSetBackUp))
        {
            removeChar(*(testStr+index), cSetBackUp);

            if(iStartIndx < 0)
            {
                iStartIndx = index;
            }
            else if( iIndexStartNext < 0)
                iIndexStartNext = index;
            else
                ;

            if (strlen(cSetBackUp) == 0 )
            {
                iEndIndx = index;
                if( iIndexStartNext == -1)
                    break;
                else
                {
                    index = iIndexStartNext;
                    ss stemp = {iStartIndx, iEndIndx, (iEndIndx-iStartIndx + 1)};
                    subStrVec.push_back(stemp);
                    iStartIndx = iEndIndx = iIndexStartNext = -1;
                    memcpy((void*)cSetBackUp, (void*)cSet, iSzSet);
                    continue;
                }
            }
        }
        else
        {
            if (IsInSet(*(testStr+index), cSet))
            {
                if(iIndexStartNext < 0)
                    iIndexStartNext = index;
            }
        }

        ++index;
    }


    int indexSmallest = 0;
    for(int indexVec = 0; indexVec < subStrVec.size(); ++indexVec)
    {
        if(subStrVec[indexSmallest].szStr > subStrVec[indexVec].szStr)
            indexSmallest = indexVec;       
    }

    subString = new char[(subStrVec[indexSmallest].szStr) + 1];
    memcpy((void*)subString, (void*)(testStr+ subStrVec[indexSmallest].iStart), subStrVec[indexSmallest].szStr);
    memset((void*)(subString + subStrVec[indexSmallest].szStr), 0, 1);

    delete[] cSetBackUp;
    return subString;
}
//--------------------------------------------------------------------

Изменить: по-видимому, существует алгоритм O(n) (см. ответ алгоритмиста). Очевидно, что это превзойдет [наивный] базовый уровень, описанный ниже!

Жаль, мне нужно идти... Я немного подозреваю, что мы можем получить O(n). Я зайду завтра, чтобы увидеть победителя ;-) Веселитесь!

Предварительный алгоритм:
Общая идея состоит в том, чтобы последовательно попытаться использовать символ из строки str2, найденный в строке str1, в качестве начала поиска (в любом/в обоих направлениях) всех остальных букв строки str2. Сохраняя значение «длина наилучшего совпадения на данный момент», мы можем прервать поиск, когда он превысит это значение. Другие эвристики, вероятно, могут быть использованы для дальнейшего прерывания неоптимальных (пока) решений. Выбор порядка начальных букв в строке str1 имеет большое значение; предлагается начать с буквы (букв) строки str1, которые имеют наименьшее количество, и попробовать с другими буквами, число которых увеличивается, в последующих попытках.

  [loose pseudo-code]
  - get count for each letter/character in str1  (number of As, Bs etc.)
  - get count for each letter in str2
  - minLen = length(str1) + 1  (the +1 indicates you're not sure all chars of 
                                str2 are in str1)
  - Starting with the letter from string2 which is found the least in string1,
    look for other letters of Str2, in either direction of str1, until you've 
    found them all (or not, at which case response = impossible => done!). 
    set x = length(corresponding substring of str1).
 - if (x < minLen), 
         set minlen = x, 
         also memorize the start/len of the str1 substring.
 - continue trying with other letters of str1 (going the up the frequency
   list in str1), but abort search as soon as length(substring of strl) 
   reaches or exceed minLen.  
   We can find a few other heuristics that would allow aborting a 
   particular search, based on [pre-calculated ?] distance between a given
   letter in str1 and some (all?) of the letters in str2.
 - the overall search terminates when minLen = length(str2) or when 
   we've used all letters of str1 (which match one letter of str2)
   as a starting point for the search

Вот реализация Java

public static String shortestSubstrContainingAllChars(String input, String target) {
    int needToFind[] = new int[256];
    int hasFound[] = new int[256];
    int totalCharCount = 0;
    String result = null;

    char[] targetCharArray = target.toCharArray();
    for (int i = 0; i < targetCharArray.length; i++) {
        needToFind[targetCharArray[i]]++;           
    }

    char[] inputCharArray = input.toCharArray();
    for (int begin = 0, end = 0; end < inputCharArray.length; end++) {

        if (needToFind[inputCharArray[end]] == 0) {
            continue;
        }

        hasFound[inputCharArray[end]]++;
        if (hasFound[inputCharArray[end]] <= needToFind[inputCharArray[end]]) {
            totalCharCount ++;
        }
        if (totalCharCount == target.length()) {
            while (needToFind[inputCharArray[begin]] == 0 
                    || hasFound[inputCharArray[begin]] > needToFind[inputCharArray[begin]]) {

                if (hasFound[inputCharArray[begin]] > needToFind[inputCharArray[begin]]) {
                    hasFound[inputCharArray[begin]]--;
                }
                begin++;
            }

            String substring = input.substring(begin, end + 1);
            if (result == null || result.length() > substring.length()) {
                result = substring;
            }
        }
    }
    return result;
}

Вот Юнит-тест

@Test
public void shortestSubstringContainingAllCharsTest() {
    String result = StringUtil.shortestSubstrContainingAllChars("acbbaca", "aba");
    assertThat(result, equalTo("baca"));

    result = StringUtil.shortestSubstrContainingAllChars("acbbADOBECODEBANCaca", "ABC");
    assertThat(result, equalTo("BANC"));

    result = StringUtil.shortestSubstrContainingAllChars("this is a test string", "tist");
    assertThat(result, equalTo("t stri"));
}

Это подход, использующий простые числа, чтобы избежать одного цикла и заменить его умножениями. Можно сделать несколько других незначительных оптимизаций.

1. Назначьте уникальное простое число любому из персонажей, которых вы хотите найти, и 1 неинтересным персонажам.

2. Найдите произведение совпадающей строки, умножив простое число на количество вхождений, которое оно должно иметь. Теперь этот продукт можно найти только в том случае, если используются одни и те же простые множители.

3. Ищите строку с самого начала, умножая соответствующее простое число по мере перехода к текущему продукту.

4. Если число больше правильной суммы, удалите первый символ и разделите его простое число на текущее произведение.

5. Если число меньше правильной суммы, включите следующий символ и умножьте его на текущий продукт.

6. Если число совпадает с правильной суммой, вы нашли совпадение, сдвиньте начало и конец к следующему символу и продолжите поиск других совпадений.

7. Определите, какая из спичек самая короткая.

Суть

charcount = { 'a': 3, 'b' : 1 };
str = "kjhdfsbabasdadaaaaasdkaaajbajerhhayeom"

def find (c, s):
  Ns = len (s)

  C = list (c.keys ())
  D = list (c.values ())

  # prime numbers assigned to the first 25 chars
  prmsi = [ 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89 , 97]

  # primes used in the key, all other set to 1
  prms = []
  Cord = [ord(c) - ord('a') for c in C]

  for e,p in enumerate(prmsi):
    if e in Cord:
      prms.append (p)
    else:
      prms.append (1)

  # Product of match
  T = 1
  for c,d in zip(C,D):
    p = prms[ord (c) - ord('a')]
    T *= p**d

  print ("T=", T)

  t = 1 # product of current string
  f = 0
  i = 0

  matches = []
  mi = 0
  mn = Ns
  mm = 0

  while i < Ns:
    k = prms[ord(s[i]) - ord ('a')]
    t *= k

    print ("testing:", s[f:i+1])

    if (t > T):
      # included too many chars: move start
      t /= prms[ord(s[f]) - ord('a')] # remove first char, usually division by 1
      f += 1 # increment start position
      t /= k # will be retested, could be replaced with bool

    elif t == T:
      # found match
      print ("FOUND match:", s[f:i+1])
      matches.append (s[f:i+1])

      if (i - f) < mn:
        mm = mi
        mn = i - f

      mi += 1

      t /= prms[ord(s[f]) - ord('a')] # remove first matching char

      # look for next match
      i += 1
      f += 1

    else:
      # no match yet, keep searching
      i += 1

  return (mm, matches)


print (find (charcount, str))

(примечание: этот ответ изначально был опубликован на повторяющийся вопрос, исходный ответ теперь удален.)

Реализация С#:

public static Tuple<int, int> FindMinSubstringWindow(string input, string pattern)
{
    Tuple<int, int> windowCoords = new Tuple<int, int>(0, input.Length - 1);
    int[] patternHist = new int[256];
    for (int i = 0; i < pattern.Length; i++)
    {
        patternHist[pattern[i]]++;
    }
    int[] inputHist = new int[256];
    int minWindowLength = int.MaxValue;
    int count = 0;
    for (int begin = 0, end = 0; end < input.Length; end++)
    {
        // Skip what's not in pattern.
        if (patternHist[input[end]] == 0)
        {
            continue;
        }
        inputHist[input[end]]++;
        // Count letters that are in pattern.
        if (inputHist[input[end]] <= patternHist[input[end]])
        {
            count++;
        }
        // Window found.
        if (count == pattern.Length)
        {
            // Remove extra instances of letters from pattern
            // or just letters that aren't part of the pattern
            // from the beginning.
            while (patternHist[input[begin]] == 0 ||
                   inputHist[input[begin]] > patternHist[input[begin]])
            {
                if (inputHist[input[begin]] > patternHist[input[begin]])
                {
                    inputHist[input[begin]]--;
                }
                begin++;
            }
            // Current window found.
            int windowLength = end - begin + 1;
            if (windowLength < minWindowLength)
            {
                windowCoords = new Tuple<int, int>(begin, end);
                minWindowLength = windowLength;
            }
        }
    }
    if (count == pattern.Length)
    {
        return windowCoords;
    }
    return null;
}

Я реализовал это с помощью Python3 с эффективностью O (N):

def get(s, alphabet="abc"):
    seen = {}
    for c in alphabet:
        seen[c] = 0
    seen[s[0]] = 1
    start = 0
    end = 0
    shortest_s = 0
    shortest_e = 99999
    while end + 1 < len(s):
        while seen[s[start]] > 1:
            seen[s[start]] -= 1
            start += 1
        # Constant time check:
        if sum(seen.values()) == len(alphabet) and all(v == 1 for v in seen.values()) and \
                shortest_e - shortest_s > end - start:
            shortest_s = start
            shortest_e = end
        end += 1
        seen[s[end]] += 1
    return s[shortest_s: shortest_e + 1]


print(get("abbcac")) # Expected to return "bca"

Решение JavaScript методом грубой силы:

function shortestSubStringOfUniqueChars(s){
	var uniqueArr = [];
	for(let i=0; i<s.length; i++){
		if(uniqueArr.indexOf(s.charAt(i)) <0){
			uniqueArr.push(s.charAt(i));
		}
	}

	let windoww = uniqueArr.length;

	while(windoww < s.length){
		for(let i=0; i<s.length - windoww; i++){
			let match = true;
			let tempArr = [];
			for(let j=0; j<uniqueArr.length; j++){
				if(uniqueArr.indexOf(s.charAt(i+j))<0){
					match = false;
					break;
				}
			}
		let checkStr
		if(match){
			checkStr =  s.substr(i, windoww);
			for(let j=0; j<uniqueArr.length; j++){
				if(uniqueArr.indexOf(checkStr.charAt(j))<0){
					match = false;
					break;
				}
			}
		}
		if(match){
		    return checkStr;
		}
 	 }
 	 windoww = windoww + 1;
	}
}

console.log(shortestSubStringOfUniqueChars("ABA"));

Код Java для описанного выше подхода:

private static Map<Character, Integer> frequency;
private static Set<Character> charsCovered;
private static Map<Character, Integer> encountered;
/**
 * To set the first match index as an intial start point
 */
private static boolean hasStarted = false;
private static int currentStartIndex = 0;
private static int finalStartIndex = 0;
private static int finalEndIndex = 0;
private static int minLen = Integer.MAX_VALUE;
private static int currentLen = 0;
/**
 * Whether we have already found the match and now looking for other
 * alternatives.
 */
private static boolean isFound = false;
private static char currentChar;

public static String findSmallestSubStringWithAllChars(String big, String small) {

    if (null == big || null == small || big.isEmpty() || small.isEmpty()) {
        return null;
    }

    frequency = new HashMap<Character, Integer>();
    instantiateFrequencyMap(small);
    charsCovered = new HashSet<Character>();
    int charsToBeCovered = frequency.size();
    encountered = new HashMap<Character, Integer>();

    for (int i = 0; i < big.length(); i++) {
        currentChar = big.charAt(i);
        if (frequency.containsKey(currentChar) && !isFound) {
            if (!hasStarted && !isFound) {
                hasStarted = true;
                currentStartIndex = i;
            }
            updateEncounteredMapAndCharsCoveredSet(currentChar);
            if (charsCovered.size() == charsToBeCovered) {
                currentLen = i - currentStartIndex;
                isFound = true;
                updateMinLength(i);
            }
        } else if (frequency.containsKey(currentChar) && isFound) {
            updateEncounteredMapAndCharsCoveredSet(currentChar);
            if (currentChar == big.charAt(currentStartIndex)) {
                encountered.put(currentChar, encountered.get(currentChar) - 1);
                currentStartIndex++;
                while (currentStartIndex < i) {
                    if (encountered.containsKey(big.charAt(currentStartIndex))
                            && encountered.get(big.charAt(currentStartIndex)) > frequency.get(big
                                    .charAt(currentStartIndex))) {
                        encountered.put(big.charAt(currentStartIndex),
                                encountered.get(big.charAt(currentStartIndex)) - 1);
                    } else if (encountered.containsKey(big.charAt(currentStartIndex))) {
                        break;
                    }
                    currentStartIndex++;
                }
            }
            currentLen = i - currentStartIndex;
            updateMinLength(i);
        }
    }
    System.out.println("start: " + finalStartIndex + " finalEnd : " + finalEndIndex);
    return big.substring(finalStartIndex, finalEndIndex + 1);
}

private static void updateMinLength(int index) {
    if (minLen > currentLen) {
        minLen = currentLen;
        finalStartIndex = currentStartIndex;
        finalEndIndex = index;
    }

}

private static void updateEncounteredMapAndCharsCoveredSet(Character currentChar) {
    if (encountered.containsKey(currentChar)) {
        encountered.put(currentChar, encountered.get(currentChar) + 1);
    } else {
        encountered.put(currentChar, 1);
    }

    if (encountered.get(currentChar) >= frequency.get(currentChar)) {
        charsCovered.add(currentChar);
    }
}

private static void instantiateFrequencyMap(String str) {

    for (char c : str.toCharArray()) {
        if (frequency.containsKey(c)) {
            frequency.put(c, frequency.get(c) + 1);
        } else {
            frequency.put(c, 1);
        }
    }

}

public static void main(String[] args) {

    String big = "this is a test string";
    String small = "tist";
    System.out.println("len: " + big.length());
    System.out.println(findSmallestSubStringWithAllChars(big, small));
}