turbokarthik
BAN USERActually according to the question, only minimum no. of elements need to be moved. But the algorithms mentioned above always move the elements to the right of the current duplicate slash, that is wrong.
For ex: /foo//baaaaaaaaaaaar. Here when we encounter the duplicate slash we are moving the string "baaaaaaaaaaaar" to its left, and that is not minimum. Ideally, the string "/foo/" needs to be moved to its right.
This can be done using partial quick sort technique.
1. Take k as the pivot element and parse the array, if there is atleast 1 element greater than k return that element. If not, go to 2,
2. Now take k/2 as pivot and parse the array, if there are atleast 2 elements greater than k/2 return those elements. Here, the output could be 0 elements greater than k/2, 1 element greater than k/2 if that is the case in the next step update no_of elements_required accordingly.
.....if we continue doing that, at the log(n) step, we will have k/2^(logn) expecting n elements if we don't get then we are done.
So the complexity is there are log(n) passes and every time we parse <= n elements. so the over all complexity is <= O(nlog(n))
Here is an algorithm.
- turbokarthik March 15, 20121. First count the total number of non-duplicate elements (non-de-count)
2. Now iterate through the array, whenever we encounter a sequence of duplicate slashes i.e. one or more slashes, calculate the non-duplicate elements to its left and non-duplicate elements to its right. How?
the current index will give the no. of non-duplicate elements to its left and non-de-count-current will give the non-duplicate elements to its right.
3. if(non-de-left <= non-de-right){
shift left characters to the right;
}else{
call removeDuplicates(str, currentStart,end);
shift right characters to the left;
}