Проверить, можно ли разбить числовую строку на подстроки с разницей между последовательными числами, равной K

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

Примеры:

Input: S = “8642”, K = 2
Output: Yes
Explanation: Split the given string as {“8”, “6”, “4”, “2”}. Now, the difference between the consecutive substrings is K(= 2).

Input: S = “1009896”, K = 0
Output: No

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

• Переберите диапазон [1, N/2], используя переменную i , и выполните следующие шаги:
  • Сохраните подстроку длины и, начиная с 0 в переменной X .
  • Сгенерируйте последовательность размера N , начиная с этого числа X , где разница последовательных терминов равна K . Сохраните эту строку в переменной test .
  • Если обе строки test и Sare равны, то обновите значение ans как true и прервите цикл.
• После выполнения вышеуказанных шагов, если значение ans равно false , выведите «No» . В противном случае выведите «Да» .

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

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