Как проверить, можно ли получить строку, используя символы другой строки в c #?

Question

Я разрабатываю проблему, в которой я хочу выяснить, сколько раз можно найти (сформировать) данную строку из другой базовой строки, при этом один символ используется только один раз.

Предположим, у меня есть

string str = "COMPUTER";

string basestr = "**TER** WITH **R** LABEL **COMPUTER** BELONGS TO **COMPUT** QUICK CUTE **COM** FOX JUM **P** S **U** R **T** H **E** LAZY DOG";

Итак, хочу, чтобы моя программа вернула 3 для этого sting basestr.Здесь один КОМПЬЮТЕР явно доступен, другой в двух словах, а последний в словах и символах.

Пожалуйста, помогите мне запрограммировать это?Как я могу это сделать ?Спасибо

Answer 1

Во-первых, построить счетчик символов для короткой строки.Затем построить счетчик символов для длинной строки.Для каждого счетчика символов короткой строки разделите счетчик из длинной строки на счетчик короткой строки, оставив только целую часть.Выберите наименьшее целое число - это ответ на вашу проблему.

int[] Count(string s) {
    int[] res = new int[256];
    foreach (var c in s) {
        res[c]++;
    }
    return res;
}
int ShortInLong(string ss, string ls) {
    var sc = Count(ss);
    var lc = Count(ls);
    int res = int.MaxValue;
    foreach (var c in ss) {
        int d = lc[c] / sc[c]; // sc[c] is never 0 because of the way we constructed it
        res = Math.Min(res, d);
    }
    return res;
}