Smallest Substring With Identical Characters II - Binary Search [JS, Java]

Description 

Solution: Binary Search

Binary search for the minimum maximum substring length.
For a length x, greedily flip characters when there are more than x consecutive identical characters.

If we get x+1 identical characters, we can flip the x+1th character.
Now this can be a problem if the x+2th character is the opposite character.
In this scenario, we can just flip the xth character instead of the x+1th.
The only case this doesn't apply is when x is 1, hence we need to deal with this case separately.

If x is 1, s has to become either "10101" or "01010". Count the number of moves to convert s into either one of these and return the minimum moves out of the two.

Time Complexity: O(n log(n))
Space Complexity: O(1)

JavaScript

function minLength(s, numOps) {
  let low = 1, high = s.length;
  while (low < high) {
    const mid = Math.floor((low + high) / 2);
    if (minMoves(s, mid) <= numOps) high = mid;
    else low = mid + 1;
  }
  return low;
};

function minMoves(s, x) {
  if (x === 1) return minMovesToAlternate(s);
  let identical = 1, moves = 0;
  for (let i = 1; i < s.length; i++) {
    if (s[i] === s[i - 1]) identical++;
    else identical = 1;
    if (identical > x) {
      moves++;
      identical = 1;
      i++;
    }
  }
  return moves;
}
  
function minMovesToAlternate(s) {
  let oneFirst = 0, zeroFirst = 0;
  for (let i = 0; i < s.length; i++) {
    if (s[i] == (i % 2)) oneFirst++;
    else zeroFirst++;
  }
  return Math.min(oneFirst, zeroFirst);
}

Java

class Solution {
    public int minLength(String s, int numOps) {
        int low = 1;
        int high = s.length();
        while (low < high) {
            int mid = (low + high) >> 1;
            if (minMoves(s, mid) <= numOps) {
                high = mid;
            } else {
                low = mid + 1;
            }
        }
        return low;
    }

    private int minMoves(String s, int x) {
        if (x == 1) {
            return minMovesToAlternate(s);
        }

        int identical = 1;
        int moves = 0;
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == s.charAt(i - 1)) {
                identical++;
            } else {
                identical = 1;
            }
            if (identical > x) {
                moves++;
                identical = 1;
                i++;
            }
        }
        return moves;
    }

    private int minMovesToAlternate(String s) {
        int oneFirst = 0;
        int zeroFirst = 0;
        for (int i = 0; i < s.length(); i++) {
            if ((s.charAt(i) - '0') == (i % 2)) {
                oneFirst++;
            } else {
                zeroFirst++;
            }
        }
        return Math.min(oneFirst, zeroFirst);
    }
}