So I was inspired by this answer, please read that answer first, the question it belongs to is basically the same as this one, except that in this question the input string is circular. The key idea in that answer is, in order to find the minimum swaps to group all 1's, we just need to get an array of all indices of 1's, the center of that array will always hold the center index, then calculate the minimum swaps by following algorithm, the time complexity is O(n):
oneIndices = array of indices of all 1's in the input
middleOfOnesIndices = round(oneIndices.length/2)-1 // index to the center index
minimumSwaps = 0
foreach index i of oneIndices
minimumSwaps += aboluteValue(oneIndices[middleOfOneIndices]-oneIndices[i])-absoluteValue(middleOfOneIndices-i);
Based on that answer, a quick solution for this question is to break the circle at some point and stretch it to be a straight line, let's say str, and then apply the above algorithm to it, then we
find the minimum swaps for str. Let n be the length of input circular string, then there are n points where we can break the circle, and the final time complexity for this solution will be O(n^2).
So I was trying to come up with a solution that takes O(n) time complexity .In the algorithm above, what determines the swaps is the relative distances between the middle 1 and the other 1's.Since we already calculated the minimum swaps for str, is there any way we can reuse it in other cases?
so we don't have to do a for-loop to calculate minimum swaps in every case, then the time complexity will be O(n).
Of all n possible points where we can break the circle, there are some points we don't need, take 100011 as the input circular string, we break it at two different points, one is between the indices 0 and 1, and the other is between 1 and 2, then we will get:
000111 and 001110
in the above algorithm, we only need to calculate the relative distances from the other 1's to the middle 1, in this two cases, what determines the minimum swaps is their common substring that contains all 1's, which is 111. So to avoid this kinda cases where we repeatedly calculate the same result, we only break the circle immediately after every 1's.
To reuse last result, we break the circle immediately after 1's from left to right orderly, take 011010110001 as an example, we first calculate the minimum swaps, then break it between indices 1 and 2, for the sake of simplicity, when we stretch the circle to be a straight line, we still keep the numbers as 0's before the point where we break the circle.
011010110001 <---before
00101011000101 <---after break it between indices 1 and 2
^^ <--- these two 0's actually don't exist, but to keep the indices of 1's to it's right
as unchanged, so we can reuse last result handily.
the array of all indices of 1's:
[1,2,4,6,7,11] <----before
[2,4,6,7,11,13] <----after break it between indices 1 and 2
My final solution written in javascript that has O(n) time complexity :
function getOneIndices(inputString) {
var oneIndices = [];
for (var i=0; i<inputString.length; i++) {
if (inputString.charAt(i) === "1") {
oneIndices.push(i);
}
}
return oneIndices;
}
function getSwapInfo(inputString) {
var oneIndices = getOneIndices(inputString);
if(oneIndices.length < 2) return 0;
var minSwaps = Number.MAX_VALUE;
var distanceInInput = 0, distanceInOneIndices = 0;
var middleOfOneIndices = Math.round(oneIndices.length/2)-1;
for (var i=0; i<oneIndices.length; i++) {
distanceInInput += Math.abs(oneIndices[middleOfOneIndices]-oneIndices[i]);
distanceInOneIndices += Math.abs(middleOfOneIndices-i);
}
for(var i = 0, lastOneIndexMoved = -1, endIndexInInput = inputString.length - 1;
i <= oneIndices.length; i++){
var curSwaps = distanceInInput - distanceInOneIndices;
if(curSwaps < minSwaps) minSwaps = curSwaps;
var lastMiddleIndex = oneIndices[middleOfOneIndices];
//move the first 1 to the end as we break the circle after it.
var firstOneIndex = oneIndices[0];
oneIndices.splice(0, 1);
var lastOneIndex = endIndexInInput + firstOneIndex - lastOneIndexMoved;
oneIndices.push(lastOneIndex);
//when we move one step further, the index of the center also move one step further,
// but the length of the indices array of 1's doesn't change, we don't
//need to do middleOfOneIndices++
var diff = oneIndices[middleOfOneIndices] - lastMiddleIndex;
distanceInInput += middleOfOneIndices * diff
- (oneIndices.length - middleOfOneIndices - 1) * diff
- Math.abs(lastMiddleIndex - firstOneIndex)
+ Math.abs(oneIndices[middleOfOneIndices] - lastOneIndex);
lastOneIndexMoved = firstOneIndex;
endIndexInInput = lastOneIndex;
}
return minSwaps;
}
console.log("minimum swaps for '111111': " + getSwapInfo("111111"));
console.log("minimum swaps for '111011': " + getSwapInfo("111011"));
console.log("minimum swaps for '010001': " + getSwapInfo("010001"));
console.log("minimum swaps for '011010110001': " + getSwapInfo("011010110001"));
console.log("minimum swaps for '10000000000000011101': " + getSwapInfo("10000000000000011101"));
console.log("minmum swaps for '01001001100': " + getSwapInfo("01001001100"));
1000111a valid sequence? – Damien