Чӣ тавр ҳалли масъала дар вақти хаттӣ O(n) бо истифода аз луғат? Дар луғат чӣ бояд нигоҳ дошта шавад, то баъдан сатрро ба тартиб дарорем? Чӣ гуна бо аломатҳое, ки дар тартиб нестанд, кор кардан мумкин аст?

Чтобы решить задачу за линейное время 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).