Длина наименьшей непростой подпоследовательности в заданной числовой строке

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

Примеры:

Input: S = “237”
Output: 2
Explanation:
There are 7 non empty subsequence {“2”, “3”, “7”, “23”, “27”, “37”, “237”}. Among these subsequence there are two subsequence that are not prime, i.e., 27 and 237. Thus as 27 has a length of 2. So print 2.

Input: S = “44444”
Output: 1

Подход: Идея решения этой проблемы основана на наблюдении, что если при удалении j или более чем j символов из строки S строка является простым числом, то ответ должен быть больше, чем j . Основываясь на этом факте, сформируйте все строки так, чтобы удаление элемента из этой строки давало простое число. Все возможные строки из приведенной выше интуиции равны {2, 3, 5, 7, 23, 37, 53, 73} . Таким образом, максимально возможный размер подпоследовательности равен 3 . Таким образом, идея состоит в том, чтобы просмотреть все подпоследовательности размера 1 и размера 2 , и если будет обнаружено, что подпоследовательности содержат хотя бы 1 элемент , которого нет в списке, тогда размер может быть либо 1 , либо 2 . В противном случае размер будет равен 3 . Выполните следующие шаги, чтобы решить проблему:

• Инициализируйте флаг логической переменной как false.
• Инициализировать фиктивную пустую строку.
• Перебрать диапазон [0, N), используя переменную j , и выполнить следующие задачи:
  • Если символ в j-й позиции не равен 2 или 3 , или 5 , или 7, то выведите ответ как 1, установите значение флага как true и break.
• Если флаг равен true , то return в противном случае выполняет следующие задачи.
• Перебрать диапазон [0, N), используя переменную j , и выполнить следующие задачи:
  • Перебрать диапазон [j+1, N), используя переменную j1 , и выполнить следующие задачи:
    • Создайте фиктивную строку с символами в позиции j и j1 .
    • Если фиктивная строка не равна 2, 3, 5, 7, 23, 37, 53 и 73 , тогда выведите ответ как 2 и установите значение флага как true и break.
• Если флаг неверен и длина строки S больше, чем равная 3 , то в качестве ответа выведите 3 , иначе выведите -1 .

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

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