Длина наименьшей непростой подпоследовательности в заданной числовой строке
Для заданной строки 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.
- Перебрать диапазон [j+1, N), используя переменную j1 , и выполнить следующие задачи:
- Если флаг неверен и длина строки S больше, чем равная 3 , то в качестве ответа выведите 3 , иначе выведите -1 .
Ниже приведена реализация вышеуказанного подхода:
Временная сложность: O(N 2 )
Вспомогательное пространство: O(1)