Your current code allocates several objects on the heap even though it doesn't need to. A string, a character array and several character objects.
Puzzles like this can often be solved not by inspecting the individual bits but by processing them in parallel. An alternative approach is:
To find the binary gap of n:
- Discard all trailing zeros.
- As long as n does not consist of 1s only:
- Combine n with n shifted to the right by one place.
- The number of repetitions is the length of the largest gap.
Taking 1000010001000 as an example:
1000010001 after 0 steps
1100011001 after 1 step
1110011101 after 2 steps
1111011111 after 3 steps
1111111111 after 4 steps
It took 4 steps, therefore the binary gap is 4.
In Java, this code becomes:
public static binaryGap(int n) {
n >>>= Integer.numberOfTrailingZeros(n);
int steps = 0;
while ((n & (n + 1)) != 0) {
n |= n >>> 1;
steps++;
}
return steps;
}
As said in the above description, this code runs in \$\mathcal O(\text{gap})\$. It can be made to run in \$\mathcal O(\log_2 \text{gap})\$ by first taking 16 steps at once, then 8, then 4, then 2, then 1. This would make the code a little longer though. For understanding the underlying concept, the above code is better than the optimized version.