Максимальное количество цифр, которые можно удалить, чтобы оставшееся целое число было согласным

Для заданной строки S , представляющей целое число из N цифр, задача состоит в том, чтобы найти максимальное количество цифр, которые можно удалить так, чтобы оставшиеся цифры были из согласного целого числа.

Обратите внимание, что 0 и 1 также считаются непростыми целыми числами.

Пример:

Input: S = “237”
Output: 1
Explanation: In the given integer, S[1] can be removed. Hence, S = “27”, which is the smallest possible integer that is non-prime. Therefore, the maximum number of digit that can be removed is 1.

Input: S = “35”
Output: -1
Explanation: It is not possible to create a non-prime integer using the above steps.

Подход: Данную проблему можно решить, используя наблюдение, что все строки, содержащие 3 или более цифр, содержат подпоследовательность цифр длины не более 2 , такую, что подпоследовательность представляет собой не простое целое число. Используя это наблюдение, данная проблема может быть решена с помощью следующих шагов:

• Создайте массив prime[] , в котором хранится, является ли данное целое число простым или нет для всех целых чисел в диапазоне [0, 100) . Этот массив можно эффективно создать с помощью Решета Эратосфена.
• Повторите заданную строку str[] и проверьте, существует ли какая-либо строка из 1 цифры, которая не является простой, то есть {0, 1, 4, 6, 8, 9} .
• Если строка из одной цифры не существует, проверьте, не меньше ли длина заданной строки <= 2 . В этом случае, если целое число, представленное S , является простым, верните -1 , иначе верните 0 .
• В противном случае верните N – 2 , что и будет требуемым ответом.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(N)
Вспомогательное пространство: O(1)