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

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

• я != Дж
• Если символ в одном из них равен «0», а в другом — «1».

Примеры :

Input: S = “100101”, K = 2
Output: 6
Explanation: Following steps can be taken: 1 -> 5 -> 6, Therefore 6th index can be reached in exactly 2 jumps

Input: S = “10111”, K = 1
Output: 2
Explanation: Following steps can be taken: 1 -> 2, Therefore 2nd index can be reached in exactly 2 jumps

Подход: Основное наблюдение проблемы состоит в том, что непрерывные комбинации нулей и единиц можно заменить одним 0 или одной единицей , потому что нельзя прыгать между похожими символами. После замены этих непрерывных шаблонов 0 и 1. Теперь можно просто проверить, говорит ли новый шаблон, что сформированная str меньше K , тогда невозможно достичь некоторой точки с K ходами, в противном случае позиция просто первая позиция справа в фактическом шаблоне, который содержит символ str[K] .

Выполните следующие шаги, чтобы решить проблему:

• Итерировать от начала до конца заданной строки i = 0 до i = N-1 и сгенерировать новую строку str после замены всех непрерывных подшаблонов из 0 на один 0 и из 1 на один 1.
• Теперь проверьте, меньше ли длина вновь сформированной строки, равной K, затем выведите -1
• В противном случае, если длина вновь сформированной строки больше K, просто напечатайте позицию символа str[K] с отсчетом от 1 справа.

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

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