Cracking the coding interview problem 5.3:

You have an integer and you can flip exactly one bit from a 0 to a 1. Write code to find the length of the longest sequence of 1s you could create.

EXAMPLE:
Input: 1775 (11011101111)
Output: 8

My first thought here is to take the approach of looking carefully at how I solve this by hand. I look at the longest string of 1s with only one zero separating them.

This would be pretty difficult to do programatically.

My second approach is the totally inefficient but works path of flipping each zero to a 1 and then checking the entire number for the largest string of 1s. This would be wildly inefficient for something like '100000000001'. But the input is not too long so performance is probably not a big concern. However, I wouldn't expect an interview to be satisfied with this algorithm.

My third path is thinking through processing in a loop one bit at a time. This path often involves a bunch of mutable state but is often the most optimized.

Here's my pseudocode I wrote on my notepad:

variables:
isSecondZero = false;
currentRun = 0;
combinedRun = 0;

while(1)
  currentRun++
  combinedRun++
  if zero, keep incrementing large until
    we hit a second zero, but reset currentRun
  if second zero, set combinedRun to currentRun

So for example '11011101111' when we hit the first zero we start counting fresh but also save up the "combined" total. When we hit another zero we save the total length and also treat it as a first zero for the next combined total.

Here's my first pass JS solution:

const findLargestRun = (binaryString) => {
  // const binaryString = num.toString(2);
  let currentRun = 0;
  let combinedRun = 0;
  let isSecondZero = false;
  let longestRun = 0;
  [...binaryString].forEach((digit) => {
    if (digit === '1') {
      currentRun++;
      combinedRun++;
      return;
    }
    if (isSecondZero) {
      longestRun = Math.max(longestRun, combinedRun);
      combinedRun = currentRun + 1;
      isSecondZero = false;
    } else {
      isSecondZero = true;
      combinedRun++;
      currentRun = 0;
    }
  });
  return Math.max(longestRun, combinedRun);
};

This works for everything except zero so I'd add an exception at the top for completeness. I also don't feel great about spreading the string into an array for the loop so I'd probably switch to a for loop for style points. I think the important part here is variable naming. It's difficult to convey the concept of resetting but also combining on the second zero.