# Smallest Substring With Identical Characters I
**Difficulty:** HARD
[External](https://leetcode.com/problems/smallest-substring-with-identical-characters-i)
Canonical: https://scaleengineer.com/dsa/problems/smallest-substring-with-identical-characters-i
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search)
**Data structures:** Array
---
## Problem
You are given a binary string `s` of length `n` and an integer `numOps`.

You are allowed to perform the following operation on `s` **at most** `numOps` times:

* Select any index `i` (where `0 <= i < n`) and **flip** `s[i]`. If `s[i] == '1'`, change `s[i]` to `'0'` and vice versa.

You need to **minimize** the length of the **longest** substring of `s` such that all the characters in the substring are **identical**.

Return the **minimum** length after the operations.

**Example 1:**

**Input:** s = "000001", numOps = 1

**Output:** 2

**Explanation:** 

By changing `s[2]` to `'1'`, `s` becomes `"001001"`. The longest substrings with identical characters are `s[0..1]` and `s[3..4]`.

**Example 2:**

**Input:** s = "0000", numOps = 2

**Output:** 1

**Explanation:** 

By changing `s[0]` and `s[2]` to `'1'`, `s` becomes `"1010"`.

**Example 3:**

**Input:** s = "0101", numOps = 0

**Output:** 1

**Constraints:**

* `1 <= n == s.length <= 1000`
* `s` consists only of `'0'` and `'1'`.
* `0 <= numOps <= n`

# Approaches
## Linear Scan on the Answer
This approach involves checking every possible answer for the minimum length, from 1 up to n. For each potential length `k`, we calculate the minimum number of flips required to ensure no substring of identical characters is longer than `k`. The first value of `k` that can be achieved with at most `numOps` flips is our answer.
**Time:** O(n^2). The outer loop runs up to `n` times. Inside the loop, the `isPossible` check function takes `O(n)` time to scan the string. · **Space:** O(1). We only use a few variables to keep track of counts and loop indices.
**Pros:** Simple and straightforward to understand and implement.; Correctly solves the problem for smaller constraints.
**Cons:** Inefficient due to the nested loop structure, leading to a quadratic time complexity.; For large `n`, this approach can be too slow and may result in a 'Time Limit Exceeded' error on some platforms.
### Explanation
The core idea is to test each possible length `k` starting from 1. Since we are looking for the *minimum* length, the first `k` that satisfies the condition will be the answer.

To check if a length `k` is achievable, we need to calculate the minimum number of operations. This involves breaking up any run of identical characters (both '0's and '1's) that is longer than `k`.

For a run of identical characters of length `len > k`, we need to introduce flips to break it into segments of length at most `k`. The most efficient way to do this is to place a flip at every `(k+1)`-th position. The number of flips required for this single run is `floor(len / (k + 1))`.

We calculate the total flips needed by summing up the flips required for all runs of '0's longer than `k` and all runs of '1's longer than `k`.

We iterate `k` from 1 to `n`. For each `k`, we compute this total required flips. If it's less than or equal to `numOps`, we've found our minimal length, and we can return `k`.

```java
class Solution {
    public int smallestSubstring(String s, int numOps) {
        int n = s.length();
        for (int k = 1; k <= n; k++) {
            if (isPossible(s, numOps, k)) {
                return k;
            }
        }
        return n; // Should not be reached given the problem constraints
    }

    private int countFlipsForChar(String s, int k, char targetChar) {
        int flips = 0;
        int currentRun = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == targetChar) {
                currentRun++;
            } else {
                if (currentRun > k) {
                    flips += currentRun / (k + 1);
                }
                currentRun = 0;
            }
        }
        if (currentRun > k) {
            flips += currentRun / (k + 1);
        }
        return flips;
    }

    private boolean isPossible(String s, int numOps, int k) {
        int requiredFlips = countFlipsForChar(s, k, '0') + countFlipsForChar(s, k, '1');
        return requiredFlips <= numOps;
    }
}
```
### Algorithm
- Loop through `k` from `1` to `n`. `k` represents the potential maximum length of an identical character substring.
- Inside the loop, calculate the total flips needed, `requiredFlips`, to satisfy the length constraint `k`.
- To calculate `requiredFlips`:
    - Initialize `requiredFlips = 0`.
    - Iterate through the string `s` to find all contiguous runs of '0's. For each run of length `len`, if `len > k`, add `len / (k + 1)` to `requiredFlips`.
    - Iterate through the string `s` again to find all contiguous runs of '1's. For each run of length `len`, if `len > k`, add `len / (k + 1)` to `requiredFlips`.
- If `requiredFlips <= numOps`, it means we can achieve a maximum run length of `k`. Since we are iterating `k` from 1 upwards, this is the smallest possible length. Return `k`.

## Binary Search on the Answer
This approach optimizes the search for the minimum length by using binary search. The key observation is that if we can achieve a maximum length of `k`, we can also achieve any length greater than `k`. This monotonic property allows us to efficiently search for the smallest `k` that satisfies the condition.
**Time:** O(n log n). The binary search runs `log n` times, and each check (`isPossible` function) takes `O(n)` time. · **Space:** O(1). We only use a few variables for the search and the check.
**Pros:** Much more efficient than the linear scan approach, especially for large `n`.; Utilizes the monotonic property of the problem to reduce the search space logarithmically.; Optimal for the given constraints.
**Cons:** Slightly more complex to conceptualize than a simple linear scan, as it requires understanding the binary search on answer pattern.
### Explanation
The problem asks for the *minimum* value of the *maximum* length. This structure is a strong indicator that binary search on the answer is a viable strategy.

We can binary search for the answer `k` in the range `[1, n]`.

For a given `k` (our `mid` in the binary search), we need a function `isPossible(k)` that checks if it's possible to make the longest run of identical characters at most `k` long using at most `numOps` flips.

This `isPossible(k)` function is the same as the one in the linear scan approach. It calculates the total flips needed to break all runs of '0's and '1's longer than `k`. The number of flips for a run of length `len` is `floor(len / (k + 1))`.

- If `isPossible(k)` is true, it means `k` is a potential answer, and we can try to find an even smaller length. So, we search in the lower half `[low, mid - 1]`.
- If `isPossible(k)` is false, `k` is too small, and we need to allow for a longer maximum length. So, we search in the upper half `[mid + 1, high]`.

We keep track of the smallest `k` for which `isPossible(k)` was true.

```java
class Solution {
    public int smallestSubstring(String s, int numOps) {
        int n = s.length();
        int low = 1, high = n;
        int ans = n;

        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (isPossible(s, numOps, mid)) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }

    private int countFlipsForChar(String s, int k, char targetChar) {
        int flips = 0;
        int currentRun = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == targetChar) {
                currentRun++;
            } else {
                if (currentRun > k) {
                    flips += currentRun / (k + 1);
                }
                currentRun = 0;
            }
        }
        if (currentRun > k) {
            flips += currentRun / (k + 1);
        }
        return flips;
    }

    private boolean isPossible(String s, int numOps, int k) {
        if (k == 0) return false; // Minimum length is 1
        int requiredFlips = countFlipsForChar(s, k, '0') + countFlipsForChar(s, k, '1');
        return requiredFlips <= numOps;
    }
}
```
### Algorithm
- Initialize the search range for the answer: `low = 1`, `high = n`.
- Initialize a variable `ans = n` to store the best possible answer found so far.
- While `low <= high`:
    - Calculate `mid = low + (high - low) / 2`.
    - Call a helper function `isPossible(mid)` which determines if a max length of `mid` is achievable with `numOps` flips.
    - The `isPossible(mid)` function calculates total flips needed for runs longer than `mid` and checks if it's `<= numOps`.
    - If `isPossible(mid)` is true:
        - `mid` is a valid length. Store it as a potential answer: `ans = mid`.
        - Try for a smaller length by narrowing the search space: `high = mid - 1`.
    - If `isPossible(mid)` is false:
        - `mid` is too small. We need a larger length: `low = mid + 1`.
- After the loop terminates, `ans` will hold the minimum possible length. Return `ans`.

# Solutions
### Java

```java
class Solution {
private
  char[] s;
private
  int numOps;
public
  int minLength(String s, int numOps) {
    this.numOps = numOps;
    this.s = s.toCharArray();
    int l = 1, r = s.length();
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
private
  boolean check(int m) {
    int cnt = 0;
    if (m == 1) {
      char[] t = {'0', '1'};
      for (int i = 0; i < s.length; ++i) {
        if (s[i] == t[i & 1]) {
          ++cnt;
        }
      }
      cnt = Math.min(cnt, s.length - cnt);
    } else {
      int k = 0;
      for (int i = 0; i < s.length; ++i) {
        ++k;
        if (i == s.length - 1 || s[i] != s[i + 1]) {
          cnt += k / (m + 1);
          k = 0;
        }
      }
    }
    return cnt <= numOps;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int minLength(string s, int numOps) {
    int n = s.size();
    auto check = [&](int m) {
      int cnt = 0;
      if (m == 1) {
        string t = "01";
        for (int i = 0; i < n; ++i) {
          if (s[i] == t[i & 1]) {
            ++cnt;
          }
        }
        cnt = min(cnt, n - cnt);
      } else {
        int k = 0;
        for (int i = 0; i < n; ++i) {
          ++k;
          if (i == n - 1 || s[i] != s[i + 1]) {
            cnt += k / (m + 1);
            k = 0;
          }
        }
      }
      return cnt <= numOps;
    };
    int l = 1, r = n;
    while (l < r) {
      int mid = (l + r) >> 1;
      if (check(mid)) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  }
};

```

### Python

```python
class Solution:
    def minLength(self, s: str, numOps: int) -> int: def check(m: int) -> bool: cnt = 0 if m == 1: t = "01" cnt = sum(c == t[i & 1] for i, c in enumerate(s)) cnt = min(cnt, n - cnt) else: k = 0 for i, c in enumerate(s): k += 1 if i == len(s) - 1 or c != s[i + 1]: cnt += k // (m + 1) k = 0 return cnt <= numOps n = len(s) return bisect_left(range(n), True, lo=1, key=check)

```