Minimize the Longest Equal-Character Substring
Company: Arista Networks
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
You are given a binary string `s` and an integer `numOps`. One operation selects an index and flips that bit: `0` becomes `1`, or `1` becomes `0`.
Using at most `numOps` operations, minimize the length of the longest contiguous substring whose characters are all identical. Return that minimum length.
```cpp
class Solution {
public:
int minLength(string s, int numOps);
};
```
### Examples
**Example 1:**
```text
Input: s = "1111110", numOps = 1
Output: 3
Explanation: Flip index 3 to obtain "1110110", whose longest identical-character substring has length 3. Reducing all such substrings to length at most 2 would require at least two flips within the six initial ones.
```
**Example 2:**
```text
Input: s = "0110", numOps = 1
Output: 2
Explanation: The original string already has longest identical-character substring length 2. The only length-1 possibilities are "0101" and "1010", and each differs from the input in two positions, exceeding the budget.
```
### Constraints
- `1 <= s.length <= 100000`.
- Every character is `0` or `1`.
- `0 <= numOps <= s.length`.
### Clarifying Questions
- Must all allowed operations be used? No; the limit is at most `numOps`.
- Does substring mean contiguous characters? Yes.
- Is the result a modified string? No, return only the minimum possible length.
- Can the answer be zero? No. The string is nonempty and flipping does not change its length.
### What a Strong Answer Covers
- Respects the flip budget and minimizes the longest identical-character substring, rather than one selected substring.
- Justifies both the feasibility and optimality of the returned length.
- Handles a single bit, no permitted flips, and enough flips to obtain length one.
- Gives bounds suitable for 100000 input characters.
### Follow-up Questions
- What must a binary string look like if its longest identical-character substring has length one?
- Why can handling neighboring substrings independently be problematic at that particular target length?
```hint Test a proposed maximum length
For a target of at least two, consider the flips needed within each original maximal equal-character run. For target one, compare the whole string with the two possible alternating patterns.
```
Overview: Minimize the longest identical-character substring of a binary string using at most a given number of bit flips. Includes examples, a proof, and a complete C++ solution.