Как проверить все ли буквы первой строки есть во второй строке?

Можно попробовать использовать хэш-таблицу (если честно уже не помню название алгоритма).

Ну или на крайняк перебором, сложность получится O(n).

Если конечно, я понял твой вопрос правильно, а то судя по коду, ты как-будто проверяешь - "Можно ли из букв 1 слова составить 2-ое слово?".

Поскольку в поправленном вопросе имеет значение число букв, то тут уже работает метод, который предложил Stanislav Volodarskiy, только знак нужно использовать <=:

Counter('abc') <= Counter('abcdef')

Если и этот вариант для вас будет недостаточно быстрым, то при достаточном кол-ве памяти есть стандартная методика, сильно ускоряющая любые операции с текстами - вынос медленных функций в отдельный метод, под кэширующий декоратор.

Например:

from functools import cache
from collections import Counter

def is_in(a, b):
    return Counter(a) <= Counter(b)

@cache
def cached_counter(x):
    return Counter(x)

def is_in_cached(a, b):
    return cached_counter(a) <= cached_counter(b)

assert is_in('aaa', 'aaaaa')
assert is_in('abd', 'abcd')
assert is_in('abc', 'cba')
assert not is_in('abc', 'ab')
assert not is_in('aaaa', 'aaa')

%timeit is_in('abc', 'abcde')
%timeit is_in_cached('abc', 'abcdef')

%timeit is_in('abc' * 10, 'abcde' * 100)
%timeit is_in_cached('abc' * 10, 'abcdef' * 100)

Вывод:

5 µs ± 175 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
2.5 µs ± 481 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)
21.7 µs ± 2.71 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)
2.08 µs ± 121 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

Для небольших строк экономия 2 раза, для больших - уже 10 раз.

В каких-то случаях можно и сравнивающую функцию взять в кэширующий декоратор:

@cache
def is_in_cached(a, b):
    return cached_counter(a) <= cached_counter(b)

Тут уже нужно смотреть - сколько у вас памяти, какая частота тех или иных слов и их сочетаний.

Например, если сами слова часто повторяются, а их сочетания практически уникальны, то брать под декоратор функцию сравнения нет смысла. Или скажем, если сочетания сравниваемых слов очень часто повторяются, то, возможно, достаточно будет взять именно сравнивающую функцию под декоратор, а вычисление счётчика - не надо.

Можно анализировать рейт попадания в кэш, чтобы понять, насколько он эффективен для каждой из функций:

ci = cached_counter.cache_info()
print(round(ci.hits/(ci.hits+ci.misses), 2))
# 1.0

Чем ближе к 1, тем кэш эффективнее. Чем ближе к 0, тем он бесполезнее.
Если кэш почти бесполезен, то лучше его вообще убрать - он только зря съест память.

Но это получается слишком медленно

Краткий анализ реализации Counter(), Modules/_collectionsmodule.c:2521 намекает, что обогнать его можно только, если сделать C реализацию для строк, а не для коллекций общего вида.

Что касается фазы сравнения, то легко видеть, что встроенный оператор >= лексикографического сравнения словарей проигрывает вашему циклу for, процентов 50...60%.

Если вероятность отрицательного ответа гораздо выше, чем положительного, то можно предварительно проверить set(w) <= set(word_2) (он же issubset()) - улучшение в три раза при удаче и ухудшение на 30% при неудаче.

особенно при многократном выполнении

Если высока доля повторений, то, как было уже предложено @CrazyElf, можно кэшировать.

Как сделать это правильно?

Если не заниматься вкусовщиной, то и так всё правильно.

Это не ответ, а скорее сценарий. Ключевой вопрос. Как сделать "правильно"?

Во-первых, поддерживать Юникод. Питон вроде бы поддерживает Юникод, т.е. с этим проблем вроде бы нет. Юникод - это набор код-пойнтов, где базовым сущностям Юникода - назначается число. Это численное значение код-пойнта.

Не вдаваясь в подробности - букве 'W' назначается число 87, а букве 'Б' назначается число 1041. И так далее. Все код-пойнты представимы числами, это диапазон 0 .. 1114111. Как с этим справляется питон - понятия не имею.

Теперь рассмотрим этот диапазон код-пойнтов, его можно разбить на блоки, собственно в самом Стандарте Юникода диапазон код-пойнтов изначально блочный. Разобьём диапазон 0-1114111 на блоки по 256 на блок.

// Буква 'W' будет попадать в блок 0.
// Потому что блок 0 - это блок код-пойнтов 0-255.

// Буква 'Б' будет попадать в блок 4.
// Потому что блок 4 - это блок код-пойнтов 1024-1279.

Иначе говоря, нужна структура памяти, или аллокатор. Это разреженный блочный аллокатор. Суть его состоять из кратных блоков, в нашем случае из блоков кратных 256. Но блоки выделяются не все, а по мере необходимости, потому такой аллокатор является разреженным.

И такой аллокатор - это набор счётчиков, на каждый встречающийся код-пойнт. Собираете два таких аллокатора на каждую входную строку, собираете количество каждого код-пойнта по значению код-пойнта. И сравниваете эти два аллокатора - получаете ответ на изначальный вопрос.

Понятное дело это всё сложно устроено и требует мощных обслуживающих оптимизаций. Для начала можно упростить, и не поддерживать весь Юникод.

Псевдокод

int charW = численное_значение_символа('W')
print(charW) // выведет 87
int charБ = численное_значение_символа('Б')
print(charБ) // выведет 1041

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

int[] блокСчётчиков0 = new int[256]; // range 0 .. 255
int[] блокСчётчиков4 = new int[256]; // range 1024 .. 1279

str строка = "какая то строка"

for (i = 0, i < строка.длина, i++)
{
    // range 0 .. 255
    if (строка[i] >= 0 && строка[i] <= 255)
    {
        // Нашли букву из латинского диапазона,
        // помещаем в латинский блок,
        // увеличиваем счётчик

        блокСчётчиков0[i]++;
    }
    // range 1024 .. 1279
    if (строка[i] >= 1024 && строка[i] <= 1279)
    {
        // Нашли букву из кириллического диапазона,
        // помещаем в кириллический блок,
        // увеличиваем счётчик

        блокСчётчиков4[i - 1024]++;
    }
    // Не обслуживаем
}

Таким образом собираются блоки счётчиков, и это очень быстро работает. А далее сравниваете значения этих блоков счётчиков.

// У вас например такой кейс "aaaa и aaa - False".
//
// В латинском блоке счётчиков первой строки
// блокСчётчиков0_дляПервойСтроки['a'] = 4 штуки
//
// В латинском блоке счётчиков второй строки
// блокСчётчиков0_дляВторойСтроки['a'] = 3 штуки

Пробегаетесь по блокам счётчиков и сравниваете их последовательно, очень быстро получаете ответ true/false.

Основная проблема здесь - это разреженный блочный аллокатор. Именно на нём должно работать. И скорее всего вам его никто не напишет, вероятность исчезающе мала, тут уже извините.

П.с.: Простейшие реализации, но на дот.нете. Переделайте на питон.

Концептуальная реализация, поддерживает основные латинский и кириллический блоки (0 .. 255, 1024 .. 1279)

int[] strA_block0_counters = new int[256];
int[] strA_block4_counters = new int[256];

int[] strB_block0_counters = new int[256];
int[] strB_block4_counters = new int[256];

string strA = "aaaa";
string strB = "aaa";

for (int i = 0; i < strA.Length; i++)
{
    if (strA[i] >= 0x0000 && strA[i] <= 0x00FF) ++strA_block0_counters[strA[i]];
    if (strA[i] >= 0x0400 && strA[i] <= 0x04FF) ++strA_block4_counters[strA[i] - 0x0400];
}
for (int i = 0; i < strB.Length; i++)
{
    if (strB[i] >= 0x0000 && strB[i] <= 0x00FF) ++strB_block0_counters[strB[i]];
    if (strB[i] >= 0x0400 && strB[i] <= 0x04FF) ++strB_block4_counters[strB[i] - 0x0400];
}

bool result = true;

for (int i = 0; i < 256; i++)
    if (strA_block0_counters[i] > strB_block0_counters[i]) { result = false; break; }
for (int i = 0; i < 256; i++)
    if (strA_block4_counters[i] > strB_block4_counters[i]) { result = false; break; }

System.Console.WriteLine(result);

// "мама мыла раму", "рама мыла маму"
// true
// "aaa", "aaaaa"
// true
// "abd", "abcd"
// true
// "abc", "cba"
// true
// "abc", "ab"
// false
// "aaaa", "aaa"
// false

Реализация на разреженном блочном аллокаторе, поддерживает 256 блоков, это диапазон Юникода 0 .. 65535. В основном его хватает, это BMP, Base Multilingual Plane. Аллокатор работает и весьма быстро, но его можно оптимизировать сильно быстрее, здесь концепция.

int[][] strA_counters = new int[256][];
int[][] strB_counters = new int[256][];

string strA = "aaaa";
string strB = "aaa";

for (int i = 0; i < strA.Length; i++)
{
    if (strA_counters[strA[i] >> 8] == null) strA_counters[strA[i] >> 8] = new int[256];
    ++strA_counters[strA[i] >> 8][(byte)strA[i]];
}
for (int i = 0; i < strB.Length; i++)
{
    if (strB_counters[strB[i] >> 8] == null) strB_counters[strB[i] >> 8] = new int[256];
    ++strB_counters[strB[i] >> 8][(byte)strB[i]];
}

bool result = true;

for (int i = 0; i < 256; i++)
    if (strA_counters[i] != null)
    {
        if (strB_counters[i] == null) { result = false; goto Result; }

        for (int j = 0; j < 256; j++)
            if (strA_counters[i][j] > strB_counters[i][j]) { result = false; goto Result; }
    }
Result:
System.Console.WriteLine(result);

// "мама мыла раму", "рама мыла маму"
// true
// "aaa", "aaaaa"
// true
// "abd", "abcd"
// true
// "abc", "cba"
// true
// "abc", "ab"
// false
// "aaaa", "aaa"
// false