Lüğət istifadə edərək, O(n) xətt vaxtında problemi necə həll etmək olar? Sonra sıralanmış bir sətir yaratmaq üçün lüğətdə nə saxlamaq lazımdır? Sıralamada olmayan simvolları necə işləmək olar?

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