779D - String Game - CodeForces Solution

#include<bits/stdc++.h>
#define ll             long long
#define pb             push_back
#define all(v)         v.begin(),v.end()
#define fr(i,s,e)      for(ll i=s;i<e;i++)
#define rfr(i,e,s)     for(ll i=e;i>=s;i--)
#define endl           "\n"
#define sz(a)          (ll)a.size()
#define mem1(a)        memset(a,-1,sizeof(a))
#define pii            pair<ll,ll>
#define ff             first
#define ss             second
#define mod            1000000000000000007
#define fast           ios_base::sync_with_stdio(0);cin.tie(NULL);cout.tie(NULL)
using namespace std;


bool check(string s , string p){
    ll d = p.size() , j = 0 ;
    for(auto x : s ){
        if(x==p[j]) j+=1;
        if(j==d) return 1 ;
    }
    return 0 ;
}

int main(){
    string s , p ;
    cin >> s >> p ;

    ll n = s.size() ;
    ll a[n+1] , lo = 1 , hi = n , res = 0 ;

    fr(i,1,n+1) cin >> a[i] ;

    while( lo <= hi ){
        ll m = (lo+hi+1)/2 , j = 0  ;
        vector<ll>v(a+1,a+m+1);
        sort(all(v));
        string ss="" , ts = s ;


        for(auto x : v ) ts[x-1]='A';
        for(auto x : ts ) if(x!='A') ss+=x;
//
//        cout << m << endl;
//        cout << ss << endl;
//        cout << check(ss,p) << endl;

        if(check(ss,p)) {
            lo = m+1 ;
            res = max(res,m);
        }
        else hi = m-1 ;
    }

    cout << res << endl;

return 0 ;
}