Maximum Number of Removable Characters LeetCode solution in C++

1
class Solution {
2
 public:
3
  bool isSubSequence(string str1, string str2) {
4
    int j = 0, m = str1.size(), n = str2.size();
5
    for (int i = 0; i < n && j < m; i++)
6
      if (str1[j] == str2[i]) j++;
7
    return (j == m);
8
  }
9
  int maximumRemovals(string s, string p, vector<int> &removable) {
10
    string copy = s;
11
    int left = 0, right = removable.size();
12
    while (left <= right) {
13
      int mid = (left + right) / 2;
14
      for (int i = 0; i < mid; i++) copy[removable[i]] = '*';
15
      if (isSubSequence(p, copy))
16
        // if p is subsequence of string after mid number of removals then we
17
        // should look for if it's possible to remove more characters
18
        left = mid + 1;
19
      else {
20
        // if p is not a subsequence of string it means that we have certainly
21
        // removed more characters from string so we must decrease our size of
22
        // removal characters and hence we  add all characters we removed
23
        // earlier.
24
        for (int i = 0; i < mid; i++) copy[removable[i]] = s[removable[i]];
25
        right = mid - 1;
26
      }
27
    }
28
    return right;
29
  }
30
};