Проверьте, имеет ли какое-либо круговое вращение String не более X 1 между двумя соседними 0

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

Примечание. Первый и последний нули в строке не считаются соседними.

Примеры:

Input: S = “010110”, X = 1        
Output: Yes 

Explanation: The 6 circular rotations of the string 
S = {“010110”, “001011”, “100101”, “110010”, “011001”, “101100”} 
out of which second , third and fourth strings satisfy the criteria.
Hence there exist a binary string which satisfy above condition.

Input:  S = “0101”, X = 0

Output: No

Эффективный подход: (без добавления вспомогательного пространства)

The input string could be thought of as a circle once we connect the last of the string to the first of it. The idea is to find out the first position of zero where the consecutive 1s between this element and the previous zero element is more than X. Next, if we need to rotate the string from that position to the left such that rest of elements in the string follows the constraints i.e. no of 1s between each pair of adjacent 0 is at most X. If we could not find any such arrangement after performing multiple rotation, then the Answer is No, else Yes. Only checking the rotation for the first incorrect position is sufficient because, there exists no right-wise circular rotation of the string such that every 2 adjacent 0′s are separated by at most X 1′s,  if there is multiple positions where the no of consecutive 1s between two consecutive 0s does not follow the strategy. This would been possible if we can rotate both clock wise (right rotation) and anti-clock wise (left rotation).

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

1. Узнайте первую позицию нуля, где он нарушает правило (ни одна из последовательных 1 между каждой парой 0 не больше X), а также отследите первую 0-ю позицию (это поможет, если существует такая позиция, где это заданное правило не выполняется )
2. Если какая-либо такая позиция нуля найдена, подсчитайте количество единиц от следующей позиции и перемещайтесь по кругу к первой позиции строки до первой нулевой позиции).
3. Если ни один из найденных последовательных 1 не превышает X, ответ НЕТ, иначе ДА

Ниже приведена реализация описанного выше подхода.

Подход: Задача может быть решена на основе следующего наблюдения:

Assuming the last character to be adjacent to first, we can find the number of ones between each pair of adjacent ones in a list. Now, the rotation of binary string is equivalent to deleting at most one element of this list. So if rest of the elements are up to X, then the answer is YES.

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

• Найдите позиции всех 0 в массиве.
• Найдите количество единиц между любыми двумя соседними нулями.
• Если существует не более 1 такого сегмента смежных единиц длины X или более, то этот сегмент может быть разделен на начальный или последний. Итак, выведите «Да»;
• В противном случае печатается «Нет».

Ниже приведена реализация описанного выше подхода.

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