Удалите необходимые элементы строки2 из строки1

Question

Рассмотрим 2 строки string1 и string2. Основная цель моего кода - удалить только элементы строки 2 из строки 1. Вот мой код

 string sring1,string2;
    cin>>string1>>string2;
     for(int i = 0; i<string2.length(); i++){
         
     string1.erase(std::remove(string1.begin(), string1.end(),string2.at(i) ), string1.end());
     }
cout<<string1;  

Проблема с приведенным выше кодом заключается в том, что он удаляет все элементы строки2 в строке1, тогда как я хочу удалить только отдельные элементы строки2 из строки1, оставив остальные как есть Вот пример вывода ВХОД: abbccdef ab c ТРЕБУЕМЫЙ ВЫХОД: bcdef МОЙ ВЫХОД: def ОГРАНИЧЕНИЯ: 1≤ | строка2 | ≤ | строка1 | ≤10 ^ 5 Пожалуйста, помогите изменить мой код.

Answer 1

Предполагая, что string1 содержит все символы из string2, вы можете сделать:

int pos = 0;  // keep track of last deleted char position

for(auto c : string2)
    string1.erase(pos = string1.find(c, pos), 1);  // update new pos and erase char

Это выполняет один линейный проход по обеим строкам. Если у вас есть символы в string2, которых нет в string1, вы можете добавить дополнительную проверку для std::string::npos.

Вот демонстрация .

Answer 2

Вы можете сделать:

#include <iostream>
#include <string>

int main() {
    std::string s1 = "abbccdef";
    std::string s2 = "abc";

    for (std::string::size_type i = 0; i < s2.length(); ++i) {
        for (std::string::size_type j = 0; j < s1.length(); ++j) {
            if (s1[j] == s2[i]) {
                s1.erase(j, 1);
                break;
            }
        }
    }

    std::cout << s1 << std::endl;
}

Вывод:

 # ./a.out 
 bcdef

EDIT

OP изменил вопрос и теперь ищет оптимальное решение этой проблемы.

Решение:

1. Запишите количество вхождений символов строки2 в массив.
2. Разберите строку1 и, если символ найден в массиве, уменьшите его количество и удалите его из строки 1.

Предположим, что размер строки 1 равен n, а размер строки 2 равен m, тогда сложность этого решения составляет O(n+m), поскольку обе строки анализируются только один раз.

#include <iostream>
#include <string>
#include <vector>

int main() {
    std::string s1 = "abbccdef";
    std::string s2 = "abc";
    std::vector<int> count(128, 0);

    for (std::string::size_type i = 0; i < s2.length(); ++i) {
        ++count[s2[i]];
    }

    std::string::size_type j = 0;
    while (j < s1.length()) {
        if (count[s1[j]] != 0) {
            --count[s1[j]];
            s1.erase(j, 1);
            continue;
        }
        ++j;
    }

    std::cout << s1 << std::endl;
    return 0;
}

Вывод:

# ./a.out
bcdef