paradox64ce

prog

Jun 17th, 2021
503
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2.  
  3. public:
  4. string s1, p1;
  5. vector<int> removable1;
  6. public:
  7.     bool check(int k){
  8.         unordered_map<int, int> mp;
  9.        
  10.         for(int i = 0;i<k;i++){
  11.             mp[removable1[i]]=1;
  12.         }
  13.        
  14.         string t="";
  15.         for(int i=0;i<s1.length();i++){
  16.             if(mp[i]){
  17.                 continue;
  18.             }
  19.             t+=s1[i];
  20.         }
  21.        
  22.         int i = 0, j = 0;
  23.         for(;i<p1.length() && j<t.length();j++){
  24.             if(t[j]==p1[i]){
  25.                 i++;
  26.             }
  27.         }
  28.        
  29.         return (i == p1.length());
  30.        
  31.     }
  32. public:
  33.     int maximumRemovals(string s, string p, vector<int>& removable) {
  34.         int n = removable.size(), ans = -1;
  35.         removable1 = removable;
  36.         s1 = s;
  37.         p1 = p;
  38.         int l = 0, r = n;
  39.         while(l<=r){
  40.             int m = (l+r)/2;
  41.             if(check(m)){
  42.                 ans = m;
  43.                 l = m + 1;
  44.             }else{
  45.                 r = m - 1;
  46.             }
  47.         }
  48.        
  49.         return ans;
  50.     }
  51. };
RAW Paste Data