Join Us
Loading Similar Posts
Entering edit mode
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool isSubsequence(string &source, string &target)
{
int i = 0, j = 0;
while (i < source.length() && j < target.length())
{
if (source[i] == target[j])
{
j++;
}
i++;
}
return j == target.length();
}
int getMaximumRemovals(vector<int> &order, string &source, string &target)
{
int start = 0;
int end = order.size(); // maximum removals
int result = 0;
while (start <= end)
{
int mid = (start + end) / 2;
// Create a mask to mark characters to be removed
vector<bool> mask(source.length(), false);
for (int i = 0; i < mid; i++)
{
mask[order[i] - 1] = true;
}
// Generate a modified source string with marked characters removed
string modifiedSource = "";
for (int i = 0; i < source.length(); i++)
{
if (!mask[i])
{
modifiedSource += source[i];
}
}
// Check if the modified source still contains the target as a subsequence
if (isSubsequence(modifiedSource, target))
{
result = mid; // Update result if it's possible to remove more characters
start = mid + 1; // Increase the number of removals
}
else
{
end = mid - 1; // Decrease the number of removals
}
}
return result;
}
int main()
{
vector<int> order = {7, 1, 2, 5, 4, 3, 6};
string source = "abbabaa";
string target = "bb";
cout << getMaximumRemovals(order, source, target) << endl; // Output: 3
return 0;
}
