#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>

using namespace std;


/*
* given a string s1 and another string s2, find the shortest substring from s1 so that the 
* substring contains all characters of s2
* the key idea is to grow a substring window until it contains all characters of s2 and then shrink the lower end of the 
* window until it fails to meet the condition.
* 
*/
string shortestSubstr(const string& s1, const string& s2) {
  vector<int> hist1(26,0);
  vector<int> hist2(26,0);
  int uniqCnt = 0;
  
  for (auto c: s2) {
    if (!hist2[c - 'a']) uniqCnt++;
    hist2[c - 'a']++;
  }
  
  int minLen = s1.size() + 1;
  string minStr;
  
  int numExist = 0;
  
  size_t i = 0, j = 0;
  
  for (; i < s1.size(); i++) {
    char c = s1[i];
    int cidx = c - 'a';
    if (hist2[cidx]) {
      hist1[cidx]++;
      if (hist1[cidx] == hist2[cidx]) {
        numExist++;
      }
    }
    if (numExist == uniqCnt) {
      int curLen = i - j + 1;
      if (curLen < minLen) {
        minLen = curLen;
        minStr = s1.substr(j,curLen);
      }
      for (; j < i; j++) {
        char c = s1[j];
        int cidx = c - 'a';
        if(hist2[cidx]) {
          hist1[cidx]--;
          if (hist1[cidx] < hist2[cidx]) {
            int curLen = i - j + 1;
            if (curLen < minLen) {
              minLen = curLen;
              minStr = s1.substr(j,i - j + 1);
            }
            numExist--;
            j++;
            break;
          }
        }
      }
    }
  }
  
  return minStr;
}

int main() {
  string s1 = "ababaaacba";
  string s2 = "abc";
  string result = shortestSubstr(s1,s2);
  cout << "shortest substring for " << s1 << " is:" << result << endl;
  return 0;
}