# STRSUB - furthur optimization

This is the link to my solution for the problem STRSUB.

The solution in the link is having time complexity of O(N + QlogN). And I am trying to solve in O(N + Q) so that each query can be solved in O(1) time. For that I am replacing the binary search in each query with preprocessed array.

Binary Search

``````Line 147: int pos= binarySearch(far, x, y, y);

private static int binarySearch(int[] far, int s, int e, int L){
int mid;
while(s<=e){
mid= (s+e) >> 1;
if(far[mid] > L){
e= mid-1;
}
else if(far[mid] <= L){
s= mid+1;
}
}
return s-1;
}
``````

with pre array

``````            int pos= pre[y];
if(pos < x) pos= x-1;
``````

This pre array is calculated through following code

``````int[] pre= new int[N];
pre= -1;
for(int i=0; i<N; i++){
pre[far[i]]= i;
}
for(int i=1; i<N; i++){
if(pre[i] == 0){
pre[i]= pre[i-1];
}
}
``````

The purpose of binary search was to find the position between ‘x’ and ‘y’ such that `far[x] <= y` so is the pre storing for each of number between ‘0 to N-1’.

But there is still something missing in `pre` which I am unable to find out which binary Search is having
and `pre` not.

Most of the test cases have passed. If some one could figure out some thing would be a great help.