that you needn't parse the Martian letters, you can keep them as opaque strings, using them as map keys

Why not? The problem is assumed to be warm-up on the contest - so any solutions with comparable asymptotics should pass without a problem

Двигаем по книге "окно" длиной со "страшное слово", проверяем чтобы кол-во каждого символа алфавита в подстроке было строго равно колв-у того же символа в "страшном слове", обновляем на -1/+1 кол-ва для первого и последнего символов соотв-о. Для быстрой проверки каждой позиции по всем символам, входящим в "страшное слово" держать массив номеров символов, причем не удовлетворяющие условию кол-ва перемещать в начало, удовлетворяющие  - в конец, тогда будет не больше двух сравнений на позицию