Tác giả: txhai12

#include <bits/stdc++.h>
using namespace std;

#define show(x) cout << (#x) << " is " << (x) << endl
#define ll long long
#define len(s) (int)s.length()
#define epb emplace_back
#define pb push_back
#define fir first
#define sed second
#define sz(ds) (int)ds.size()
#define all(arr) arr.begin(), arr.end()
#define endl '\n'
#define mp(a,b) make_pair(a,b)

const int maxn = 1e5 + 5;
int cnt[30][maxn];
vector<int> pos[30];

int main() {
  //ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  string s, t;
  cin >> s >> t;
  s = " " + s;
  int ns = len(s);
  int nt = len(t);


  for (int i = 1 ; i < ns ; i++) {
    pos[ s[i] - 'a' ].epb(i);

    for (int j = 0 ; j < 26 ; j++) {
      cnt[j][i] = cnt[j][i - 1] + (s[i] - 'a' == j);
    }

  }

  vector<int> cnt_t(26, 0);
  for (auto c : t) {
    cnt_t[c - 'a']++;
  }

  // for(int i = 0 ; i < ns ; i++){
  //   for(int j = 0 ; j < 26 ; j++){
  //     cout<<cnt[j][i]<<" ";
  //   }
  //   cout<<endl;
  // }

  sort(all(t));

  vector<bool> done(nt, false);

  string ans = "";
  int cur = 0;
  while (len(ans) < nt) {
    bool ok = false;

    for (int j = 0 ; j < nt ; j++) {
      if (done[j]) continue;

      int idxc = t[j] - 'a';

      int id_s = lower_bound( pos[idxc].begin(), pos[idxc].end(), cur) - pos[idxc].begin();

      if (id_s == sz(pos[idxc])){
        continue;
      }

      int rem_ok = true;

      done[j] = true;
      cnt_t[ idxc ]--;
      int p = pos[idxc][id_s] + 1;

      for (int i = 0 ; i < 26 ; i++) {
        if ( cnt_t[i] > cnt[i][ns - 1] - cnt[i][p - 1] ) {
          rem_ok = false;
          break;
        }
      }

      if (rem_ok) {
        ans += (char)(idxc + 'a');
        ok = true;
        cur = p;
        break;
      } else {
        done[j] = false;
        cnt_t[ idxc ]++;
      }

    }


    if (ok == false) {
      cout << -1;
      return 0;
    }


  }



  cout << ans << endl;

  // string st = t;
  // sort(st.begin(),st.end());
  // show(st);


}