Hoe los je een probleem op in lineaire tijd O(n) met behulp van een woordenboek? Wat moet er in het woordenboek worden opgeslagen om later een gesorteerde string te maken? Hoe ga je om met tekens die niet in de volgorde staan?

Чтобы решить задачу за линейное время O(n) с помощью словаря (хэша), нужно:

1. Подсчитать количество каждого символа в исходной строке и сохранить в словаре, где ключ — символ, значение — количество.

2. Итерироваться по строке order, для каждого символа брать из словаря его количество и добавлять этот символ столько раз в результат.

3. Обработать символы, которых нет в order — пройтись по словарю и добавить оставшиеся символы в любом порядке (например, в порядке появления).

Пример на Python:

from collections import Counter

def custom_sort(s: str, order: str) -> str:
    count = Counter(s)
    result = []

    for ch in order:
        if ch in count:
            result.append(ch * count[ch])
            del count[ch]

    # Добавляем символы, которых нет в order
    for ch, cnt in count.items():
        result.append(ch * cnt)

    return ''.join(result)

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