Лексикографически максимальная подстрока будет начинаться с самого большого (в алфавитном порядке) символа исходной строки. Если одна строка является префиксом другой, то эта вторая строка будет лексикографически большей. Поэтому выгоднее выбирать максимальную подстроку начиная с самых левых символов. И при этом подстрока всегда должна заканчиваться последним символом исходной строки.
Поэтому можно перебрать левый символ подстроки и сравнивать полученную подстроку с текущим наилучшим вариантом. Если новая подстрока будет больше, то записать в текущий вариант ее.
Время работы программы составит O(N^2), где N – длина строки. Для N в пределах 1000 программа будет укладываться во временные ограничения.
Поэтому можно перебрать левый символ подстроки и сравнивать полученную подстроку с текущим наилучшим вариантом. Если новая подстрока будет больше, то записать в текущий вариант ее.
Время работы программы составит O(N^2), где N – длина строки. Для N в пределах 1000 программа будет укладываться во временные ограничения.