У Ирохи есть последовательность из N строк s1, s2, .., sN. Каждая строка длиной L. Ироха хочет объединить все строки, чтобы получить очень длинную строку. Среди всех строк, которые она может получить таким образом, найдите лексикографически наименьшую. Будем считать, что строка s = s1s2…sn лексикографически меньше строки t = t1t2…tm, если выполняется одно из следующих условий: – существует индекс i ((1<=i<=min(n,m))), такой что (s_j =t_j ), для всех индексов j ((1<=j<=i)), и (s_i <t

Решаем задачу с помощью сортировки.

Шаг 1: Создаем функцию compare, которая будет сравнивать две строки. Пока строки имеют одинаковую длину, мы сравниваем их лексикографически. Если строки разной длины, мы сравниваем префиксы строк длиной равной длине короткой строки.

Шаг 2: Создаем массив строк и заполняем его данными.

Шаг 3: Сортируем массив строк с помощью функции сравнения compare.

Шаг 4: Объединяем строки в одну очень длинную строку, начиная с самой маленькой строки.

Шаг 5: Возвращаем полученную очень длинную строку.

Алгоритм имеет сложность O(N*L*log(N)), где N – количество строк, а L – длина каждой строки. Так как нам нужно только вернуть лексикографически наименьшую строку, а не все строки отсортированные, то мы не сортируем массив полностью, а используем сортировку слиянием, что дает нам возможность провести сортировку за O(N*L*log(N)).