Given a bit string S i.e containing "0" and "1" only. You can perform K number of operations (K>0) in an iterative way, always starting from K=1, in the following manner:-
when K=1, remove one leftmost bit and append it to right.
when K=2, remove two leftmost bit one by one and append it to right one by one.
when K=3, remove three left most bit one by one and append it to right one by one.
when K=4, remove four left most bit one by one and append it to right one by one.
so on...
You have to print the minimum value of K (K > 0) so that we get our original input string S after K number of operations.
Input format :-
A sigle string S.
Output format :-
Print minimum value of K.
Constraints:-
2<=length of string<=10^5
Example:-
Input 1:-
1011
Output:-
7
Input 2:-
1101
Output:-
7
Input 3:-
11011
Output:-
4
Input 4:-
11010
Output:-
4
Input 5:-
01010
Output:-
4
Input 6:-
101010
Output:-
3
Input 7:-
111001
Output:-
3
Explanations:-
In 1st input S=1011, so starting from K=1,
K=1 , S=0111 (1011 -> 0111)
K=2 , S=1101 (0111 -> 1110 -> 1101)
K=3 , S=1110 (1101 -> 1011 -> 0111 -> 1110)
K=4 , S=1110 (1110 -> 1101 -> 1011 -> 0111 -> 1110)
K=5 , S=1101 (1110 -> 1101 -> 1011 -> 0111 -> 1110 -> 1101)
K=6 , S=0111 (1101 -> 1011 -> 0111 -> 1110 -> 1101 -> 1011 -> 0111)
K=7 , S=1011 (0111 -> 1110 -> 1101 -> 1011 -> 0111 -> 1110 -> 1101 -> 1011)
so answer is K=7.
Can you post the problem source?