Недавно я принимал участие в каком-то онлайн-тесте на языке Java.
В одном из вопросов меня попросили реализовать функцию, которая при наличии строки возвращает минимальное количество символов, которое должнобыть удаленным из строки, чтобы получить новую лексикографическую упорядоченную строку.
Это означает, что, когда мы передаем строку "банан" нашему методу, он вернет 3.
Из слова "банан" нам нужноубрать 1-ю букву ("b"), 3-ю букву ("n") и 6-ю букву ("a"), чтобы получить строку "aan".
Нет возможности удалить меньше букв.
Я пытался найти решение довольно долго, но безрезультатно.
Единственное, что могло бы сработать, - это проверить каждую возможную подстроку из нашей исходной строки, проверить, упорядочена ли она, и сравнить количество удаленных цифр, но это было бы ужасно для более длинных строк.
Есть идеи для алгоритма?